c++&oi
网络流24题-1
二分图最大匹配
匈牙利算法无压力
#include
<
cstdio
>
#include
<
cstring
>
bool
way[
201
][
201
];
int
link[
201
];
bool
used[
201
];
int
count
=
0
;
int
path(
int
u);
int
n,m;
int
main()
{
freopen(
"
air.in
"
,
"
r
"
,stdin);
freopen(
"
air.out
"
,
"
w
"
,stdout);
int
a,b;
scanf(
"
%d %d
"
,
&
n,
&
m);
m
-=
n;
memset(way,
false
,
sizeof
(way));
for
(;;)
{
scanf(
"
%d %d
"
,
&
a,
&
b);
if
(a
!=-
1
&&
b
!=-
1
)
way[a][b
-
n]
=
true
;
else
break
;
}
memset(link,
0
,
sizeof
(link));
for
(
int
i
=
1
;i
<=
n;i
++
)
{
memset(used,
false
,
sizeof
(used));
if
(path(i))
count
++
;
}
printf(
"
%d\n
"
,count);
for
(
int
i
=
1
;i
<=
m;i
++
)
if
(link[i])
printf(
"
%d %d\n
"
,link[i],i
+
n);
fclose(stdin);
fclose(stdout);
return
0
;
}
int
path(
int
u)
{
for
(
int
v
=
1
;v
<=
m;v
++
)
if
(way[u][v]
&&!
used[v])
{
used[v]
=
true
;
if
(
!
link[v]
||
path(link[v]))
{
link[v]
=
u;
return
true
;
}
}
return
false
;
}
Dinic全数组版
#include
<
cstdio
>
#include
<
cstring
>
#include
<
cstdlib
>
//
max__:数组大小，数据上界的常量
//
大写英文开头:常用小数据结构（Queue\Hash\Father\Stack\Matrix）
//
小写英文：主数据结构(一般是图或平衡树)、单个变量
//
全大写：特殊符号、宏定义
//
head点的边表头，Head队列头
//
const
int
maxn
=
301
;
const
int
maxm
=
300001
;
const
int
maxnum
=
0x7FFFFFFF
;
//
int
Queue[maxm],Head,Tail;
//
int
to[maxm],next[maxm],sc[maxm],snum
=
0
;
int
level[maxn],head[maxn],
out
[maxn];
//
void
init();
void
insert(
int
x,
int
y,
int
c);
void
max_flow(
int
n,
int
s,
int
t);
//
int
main()
{
freopen(
"
air.in
"
,
"
r
"
,stdin);
freopen(
"
air.out
"
,
"
w
"
,stdout);
int
n,m;
scanf(
"
%d %d
"
,
&
m,
&
n);
init();
int
a,b;
int
s
=
n
+
1
,t
=
n
+
2
;
for
(
int
i
=
1
;i
<=
m;i
++
)
insert(s,i,
1
);
for
(
int
i
=
m
+
1
;i
<=
n;i
++
)
insert(i,t,
1
);
for
(;scanf(
"
%d %d
"
,
&
a,
&
b)
!=
EOF;)
if
(a
!=-
1
)
insert(a,b,
1
);
else
break
;
max_flow(n
+
2
,s,t);
fclose(stdin);
fclose(stdout);
return
0
;
}
void
init()
{
snum
=
1
;
//
for ^
memset(head,
0
,
sizeof
(head));
}
void
insert(
int
x,
int
y,
int
c)
{
snum
++
;
to[snum]
=
y;
sc[snum]
=
c;
next[snum]
=
head[x];
head[x]
=
snum;
snum
++
;
to[snum]
=
x;
sc[snum]
=
0
;
next[snum]
=
head[y];
head[y]
=
snum;
}
void
max_flow(
int
n,
int
s,
int
t)
{
int
flow
=
0
,cur;
for
(;;)
{
memset(level,
0
,
sizeof
(level));
Head
=
Tail
=
1
;
level[s]
=
1
;
Queue[Head]
=
s;
for
(;Head
<=
Tail;Head
++
)
{
int
t
=
Queue[Head];
for
(
int
p
=
head[t];p;p
=
next[p])
if
(sc[p]
&&!
level[to[p]])
{
Tail
++
;
level[to[p]]
=
level[t]
+
1
;
Queue[Tail]
=
to[p];
}
}
if
(level[t]
==
0
)
break
;
for
(
int
i
=
1
;i
<=
n;i
++
)
out
[i]
=
head[i];
int
q
=
0
;
for
(;;)
{
if
(
!
q)
{
for
(cur
=
out
[s];cur;cur
=
next[cur])
if
(sc[cur]
&&
out
[to[cur]]
&&
level[to[cur]]
==
2
)
break
;
if
(cur)
{
q
++
;
Queue[q]
=
cur;
out
[s]
=
next[cur];
}
else
break
;
}
int
u
=
to[Queue[q]];
if
(u
==
t)
{
int
dd
=
maxnum;
int
ddl
=
0
;
for
(
int
i
=
1
;i
<=
q;i
++
)
if
(dd
>
sc[Queue[i]])
{
dd
=
sc[Queue[i]];
ddl
=
i;
}
flow
+=
dd;
for
(
int
i
=
1
;i
<=
q;i
++
)
{
sc[Queue[i]]
-=
dd;
sc[Queue[i]
^
1
]
+=
dd;
}
for
(
int
i
=
1
;i
<=
q;i
++
)
if
(
!
sc[Queue[i]])
{
q
=
ddl
-
1
;
break
;
}
}
else
{
for
(cur
=
out
[u];cur;cur
=
next[cur])
if
(sc[cur]
&&
out
[to[cur]]
&&
level[u]
+
1
==
level[to[cur]])
break
;
if
(cur)
{
q
++
;
Queue[q]
=
cur;
out
[u]
=
next[cur];
}
else
{
out
[u]
=
0
;
q
--
;
}
}
}
}
printf(
"
%d\n
"
,flow);
memset(level,
0
,
sizeof
(level));
Head
=
Tail
=
1
;
level[s]
=
1
;
Queue[Head]
=
s;
for
(;Head
<=
Tail;Head
++
)
{
int
t
=
Queue[Head];
for
(
int
p
=
head[t];p;p
=
next[p])
{
if
(level[t]
==
2
&&
to[p]
!=
s
&&!
sc[p])
printf(
"
%d %d\n
"
,t,to[p]);
if
(
!
level[to[p]])
{
Tail
++
;
level[to[p]]
=
level[t]
+
1
;
Queue[Tail]
=
to[p];
}
}
}
}
很无奈，自己写了judge
#include
<
cstdio
>
#include
<
cstdlib
>
#include
<
cstring
>
FILE
*
fscore,
*
freport,
*
fstd,
*
fin,
*
fout;
int
a
=
1
,b
=
1
;
int
n,m;
int
aa
=
0
,bb
=
0
;
bool
way[
201
][
201
];
bool
usex[
201
];
bool
usey[
201
];
int
score;
void
Judge()
{
int
a,b;
fscanf(fin,
"
%d %d
"
,
&
n,
&
m);
m
-=
n;
memset(way,
false
,
sizeof
(way));
memset(usex,
false
,
sizeof
(usex));
memset(usey,
false
,
sizeof
(usey));
for
(;;)
{
fscanf(fin,
"
%d %d
"
,
&
a,
&
b);
if
(a
!=-
1
&&
b
!=-
1
)
way[a][b
-
n]
=
true
;
else
break
;
}
fscanf(fout,
"
%d
"
,
&
a);
fscanf(fstd,
"
%d
"
,
&
b);
if
(a
!=
b)
{
fprintf(fscore,
"
%d
"
,
0
);
fprintf(freport,
"
Wrong number of matches\n
"
);
return
;
}
for
(
int
i
=
a;i
>=
1
;i
--
)
{
fscanf(fout,
"
%d %d
"
,
&
a,
&
b);
b
-=
n;
if
(
!
way[a][b])
{
fprintf(fscore,
"
%d
"
,score
/
2
);
fprintf(freport,
"
Wrong match！\n
"
);
return
;
}
if
(usex[a])
{
fprintf(fscore,
"
%d
"
,score
/
2
);
fprintf(freport,
"
Wrong match！\n
"
);
return
;
}
else
usex[a]
=
false
;
if
(usey[b])
{
fprintf(fscore,
"
%d
"
,score
/
2
);
fprintf(freport,
"
Wrong match！\n
"
);
return
;
}
else
usey[b]
=
false
;
}
fprintf(fscore,
"
%d
"
,score);
}
int
main(
int
argc,
char
*
argv[])
{
fscore
=
fopen(
"
score.log
"
,
"
w
"
);
//
打开得分文件
freport
=
fopen(
"
report.log
"
,
"
w
"
);
//
打开报告文件
fstd
=
fopen(argv[
2
],
"
r
"
);
//
打开测试点标准输出文件
score
=
atoi(argv[
1
]);
//
取得测试点的分数
fin
=
fopen(
"
air.in
"
,
"
r
"
);
fout
=
fopen(
"
air.out
"
,
"
r
"
);
Judge();
fclose(fscore);
//
关闭得分文件
fclose(freport);
//
关闭报告文件
return
0
;
}
posted on 2012-02-18 16:49
zyn.cpp
阅读(215)
评论(0)
编辑
收藏
引用
只有注册用户
登录
后才能发表评论。
网站导航:
博客园
IT新闻
BlogJava
知识库
博问
管理
<
2012年2月
>
日
一
二
三
四
五
六
29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
1
2
3
4
5
6
7
8
9
10
导航
C++博客
首页
新随笔
联系
聚合
管理
统计
随笔 - 57
文章 - 13
评论 - 11
引用 - 0
常用链接
我的随笔
我的评论
我参与的随笔
留言簿
给我留言
查看公开留言
查看私人留言
随笔档案
(57)
2012年6月 (2)
2012年5月 (4)
2012年4月 (18)
2012年3月 (7)
2012年2月 (14)
2012年1月 (3)
2011年12月 (8)
2011年11月 (1)
文章档案
(13)
2012年2月 (1)
2011年12月 (7)
2011年11月 (1)
2011年9月 (3)
2011年8月 (1)
搜索
最新评论
1. re: 培训作业-第三周（STL&USACO+4）
评论内容较长,点击标题查看
--佛教网
2. re: 培训作业-第三周（STL&USACO+4）
评论内容较长,点击标题查看
--happem
3. re: NOIP2011解题报告
sum[i]表示前i个点的单位数?这。。，sum[i]表示i点前下车的乘客数吧？
--锐
4. re: NOIP2011解题报告
顶一下。。
--锐
5. re: 培训作业-第三周（STL&USACO+4）
@zyn.cpp
用vector暴力平衡树啊。。。
--姚京韬
阅读排行榜
1. NOIP2011普及组的第三题：瑞士轮(2548)
2. NOI LINUX 安装记(1954)
3. 随便说说状态压缩(1502)
4. 迎接初中同学——整理OI知识点（building）(797)
5. POJ 1733 (545)
评论排行榜
1. 培训作业-第三周（STL&USACO+4）(5)
2. NOIP2011普及组的第三题：瑞士轮(2)
3. POJ 1733 (1)
4. 网络流24题-1(0)
5. usaco4.1.2(0)
Powered by:
C++博客
Copyright © zyn.cpp