BZOJ

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.