BZOJ 2150

传送门

$最小路径覆盖=\mid P \mid - 最大匹配$

二分图最大匹配
网络流

其实两个方法差不多,只是建的图有点区别

都是如果能走就向下连边,然后直接求最大匹配

但是这道题的${\rm Hungary}$真的好快啊QAQ

Hungary

这个建了个二分图…


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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
program bzoj_2150;
var num:array[1..50,1..50]of longint;
pair,lst:array[1..5000]of longint;
v:array[1..5000]of boolean;
l:array[1..10000]of record ed,pre:longint; end;
n,m,r,c,i,j,cnt,tot,ans:longint;
ch:char;
procedure link(a,b:longint);
begin
inc(tot);
l[tot].pre:=lst[a];
lst[a]:=tot;
l[tot].ed:=b;
end;
function check(x,y:longint):boolean;
begin
exit((x>0)and(x<=m)and(y>0)and(y<=n)and(num[x,y]<>0));
end;
function hungary(x:longint):boolean;
var k:longint;
begin
k:=lst[x];
while k<>0 do
begin
if not v[l[k].ed] then
begin
v[l[k].ed]:=true;
if (pair[l[k].ed]=0)or(hungary(pair[l[k].ed])) then
begin
pair[l[k].ed]:=x;
exit(true);
end;
end;
k:=l[k].pre;
end;
exit(false);
end;
begin
readln(m,n,r,c);
cnt:=0;
for i:=1 to m do
begin
for j:=1 to n do
begin
read(ch);
if ch='.' then
begin
inc(cnt);
num[i,j]:=cnt;
end;
end;
readln;
end;
for i:=1 to m do
for j:=1 to n do
begin
if num[i,j]=0 then continue;
if check(i+r,j-c) then link(num[i,j],cnt+num[i+r,j-c]);
if check(i+r,j+c) then link(num[i,j],cnt+num[i+r,j+c]);
if check(i+c,j-r) then link(num[i,j],cnt+num[i+c,j-r]);
if check(i+c,j+r) then link(num[i,j],cnt+num[i+c,j+r]);
end;
ans:=0;
for i:=1 to cnt do
begin
fillchar(v,sizeof(v),false);
if hungary(i) then inc(ans);
end;
writeln(cnt-ans);
end.

Dinic

这个是一个矩阵图…


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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
program bzoj_2150;
const inf=maxlongint>>1;
qs=100000;
var d,lst,que:array[0..10010]of longint;
v:array[0..10010]of boolean;
l:array[0..5000000]of record f,ed,pre:longint; end;
q:array[0..qs]of longint;
n,m,r,c,i,j,ss,tt,hd,tl,maxf,tot,cnt,len:longint;
ch:char;
pd:array[0..100,0..100]of boolean;
function min(a,b:longint):longint;
begin
if a<b then exit(a) else exit(b);
end;
procedure ad(a,b,f:longint);
begin
inc(tot);
l[tot].pre:=lst[a];
lst[a]:=tot;
l[tot].ed:=b;
l[tot].f:=f;
end;
procedure link(x,y,a,b:longint);
begin
if (a>m)or(b<1)or(b>n)or(not pd[a,b]) then exit;
ad((x-1)*n+y+m*n,(a-1)*n+b,1);
ad((a-1)*n+b,(x-1)*n+y+m*n,0);
end;
function spfa:boolean;
var k:longint;
begin
fillchar(v,sizeof(v),false);
fillchar(d,sizeof(d),$7f);
hd:=0;
tl:=1;
q[1]:=ss;
d[ss]:=0;
v[ss]:=true;
while hd<>tl do
begin
inc(hd);
if hd>qs then hd:=1;
k:=lst[q[hd]];
while k<>0 do
begin
if (l[k].f>0)and(d[q[hd]]+1<d[l[k].ed]) then
begin
d[l[k].ed]:=d[q[hd]]+1;
if not v[l[k].ed] then
begin
inc(tl);
if tl>qs then tl:=1;
q[tl]:=l[k].ed;
v[l[k].ed]:=true;
end;
end;
k:=l[k].pre;
end;
v[q[hd]]:=false;
end;
fillchar(v,sizeof(v),false);
exit(d[tt]<inf);
end;
procedure expand;
var i,f:longint;
begin
f:=inf;
for i:=1 to len do if l[que[i]].f<f then f:=l[que[i]].f;
inc(maxf,f);
for i:=1 to len do
begin
dec(l[que[i]].f,f);
inc(l[que[i] xor 1].f,f);
end;
end;
procedure dfs(t:longint);
var k:longint;
begin
v[t]:=true;
if t=tt then
begin
expand;
exit;
end;
k:=lst[t];
while k<>0 do
begin
if (l[k].f>0)and(d[l[k].ed]=d[t]+1)and(not v[l[k].ed]) then
begin
inc(len);
que[len]:=k;
dfs(l[k].ed);
dec(len);
end;
k:=l[k].pre;
end;
end;
begin
readln(m,n,r,c);
ss:=2*m*n+1;
tt:=2*m*n+2;
for i:=1 to m do
begin
for j:=1 to n do
begin
read(ch);
pd[i,j]:=(ch='.');
end;
readln;
end;
cnt:=0;
tot:=1;
for i:=1 to m do
for j:=1 to n do
begin
if not pd[i,j] then continue;
inc(cnt);
link(i,j,i+r,j-c);
link(i,j,i+r,j+c);
ad((i-1)*n+j,tt,1);
ad(tt,(i-1)*n+j,0);
ad(ss,(i-1)*n+j+m*n,1);
ad((i-1)*n+j+m*n,ss,0);
link(i,j,i+c,j-r);
link(i,j,i+c,j+r);
end;
maxf:=0;
while spfa do dfs(ss);
writeln(cnt-maxf);
end.