首页 > 代码库 > AHOI2009最小割
AHOI2009最小割
1797: [Ahoi2009]Mincut 最小割
Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 1072 Solved: 446
[Submit][Status]
Description
Input
Output
Sample Input
1 2 3
1 3 2
2 4 4
2 5 1
3 5 5
4 6 2
5 6 3
Sample Output
1 0
0 0
1 0
0 0
1 0
1 0
HINT
设第(i+1)行输入的边为i号边，那么{1,2},{6,7},{2,4,6}是仅有的三个最小代价切割方案。它们的并是{1,2,4,6,7}，交是 。
【数据规模和约定】
测试数据规模如下表所示
数据编号 N M 数据编号 N M
1 10 50 6 1000 20000
2 20 200 7 1000 40000
3 200 2000 8 2000 50000
4 200 2000 9 3000 60000
5 1000 20000 10 4000 60000
Source
Day1
题解：摘自jcvb
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------
一个有向图，源点s，汇点t，问哪些边能够出现在某个最小割集中，哪些边必定出现在最小割集中。
求最大流，在残余网络上跑tarjan求出所有SCC，记id[u]为点u所在SCC的编号。显然有id[s]!=id[t]（否则s到t有通路，能继续增广）。
①对于任意一条满流边(u,v)，(u,v)能够出现在某个最小割集中，当且仅当id[u]!=id[v]；
②对于任意一条满流边(u,v)，(u,v)必定出现在最小割集中，当且仅当id[u]==id[s]且id[v]==id[t]。
简要写一下证明：
首先，由最大流最小割定理易知最小割中的割边一定是满流边。
①
==>如果id[u]==id[v]，则残余网络存在u->v的通路，通过(u,v)的割也必然通过这条通路上的某条非满流边，不会是最小割。（update:QAQ后来发现这个证明有问题。。。到时候再想想）
<==将每个SCC缩成一个点，得到的新图就只含有满流边了。那么新图的任一s-t割都对应原图的某个最小割，从中任取一个把id[u]和id[v]割开的割即可证明。
②
<==：假设将(u,v)的边权增大，那么残余网络中会出现s->u->v->t的通路，从而能继续增广，于是最大流流量（也就是最小割容量）会增大。这即说明(u,v)是最小割集中必须出现的边。
==>：上面的证明可以反推回去，略。
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------
结论是正确的，可以AC
代码：
1 const inf=maxlongint; 2 type node=record 3 from,go,next,v:longint; 4 end; 5 var tot,i,j,n,m,maxflow,l,r,s,t,x,y,z,ti,top,cnt,xx,yy:longint; 6 h,head,q,cur,low,dfn,sta,scc:array[0..10000] of longint; 7 e:array[0..200000] of node; 8 function min(x,y:longint):longint; 9 begin 10 if x<y then exit(x) else exit(y); 11 end; 12 procedure ins(x,y,z:longint); 13 begin 14 inc(tot); 15 e[tot].from:=x;e[tot].go:=y;e[tot].v:=z;e[tot].next:=head[x];head[x]:=tot; 16 end; 17 procedure insert(x,y,z:longint); 18 begin 19 ins(x,y,z);ins(y,x,0); 20 end; 21 function bfs:boolean; 22 var i,x,y:longint; 23 begin 24 fillchar(h,sizeof(h),0); 25 l:=0;r:=1;q[1]:=s;h[s]:=1; 26 while l<r do 27 begin 28 inc(l); 29 x:=q[l]; 30 i:=head[x]; 31 while i<>0 do 32 begin 33 y:=e[i].go; 34 if (e[i].v<>0) and (h[y]=0) then 35 begin 36 h[y]:=h[x]+1; 37 inc(r);q[r]:=y; 38 end; 39 i:=e[i].next; 40 end; 41 end; 42 exit (h[t]<>0); 43 end; 44 function dfs(x,f:longint):longint; 45 var i,y,used,tmp:longint; 46 begin 47 if x=t then exit(f); 48 used:=0; 49 i:=cur[x]; 50 while i<>0 do 51 begin 52 y:=e[i].go; 53 if (h[y]=h[x]+1) and (e[i].v<>0) then 54 begin 55 tmp:=dfs(y,min(e[i].v,f-used)); 56 dec(e[i].v,tmp);if e[i].v<>0 then cur[x]:=i; 57 inc(e[i xor 1].v,tmp); 58 inc(used,tmp); 59 if used=f then exit(f); 60 end; 61 i:=e[i].next; 62 end; 63 if used=0 then h[x]:=-1; 64 exit(used); 65 end; 66 procedure dinic; 67 begin 68 while bfs do 69 begin 70 for i:=1 to n do cur[i]:=head[i]; 71 inc(maxflow,dfs(s,inf)); 72 end; 73 end; 74 procedure init; 75 begin 76 tot:=1; 77 readln(n,m,s,t); 78 for i:=1 to m do 79 begin 80 readln(x,y,z); 81 insert(x,y,z); 82 end; 83 end; 84 procedure dfs(x:longint); 85 var i,y,z:longint; 86 begin 87 inc(ti);dfn[x]:=ti;low[x]:=ti;inc(top);sta[top]:=x; 88 i:=head[x]; 89 while i<>0 do 90 begin 91 y:=e[i].go; 92 if e[i].v<>0 then 93 begin 94 if dfn[y]=0 then 95 begin 96 dfs(y); 97 low[x]:=min(low[x],low[y]); 98 end 99 else if scc[y]=0 then low[x]:=min(low[x],dfn[y]);100 end;101 i:=e[i].next;102 end;103 if low[x]=dfn[x] then104 begin105 inc(cnt);106 while true do107 begin108 z:=sta[top];dec(top);109 scc[z]:=cnt;110 if z=x then break;111 end;112 end;113 end;114 procedure tarjan;115 begin116 ti:=0;cnt:=0;ti:=0;117 fillchar(dfn,sizeof(dfn),0);118 for i:=1 to n do if dfn[i]=0 then dfs(i);119 end;120 procedure main;121 begin122 dinic;123 tarjan;124 x:=scc[s];y:=scc[t];125 for i:=2 to tot do126 if (i and 1=0) then127 begin128 if e[i].v<>0 then begin writeln(‘0 0‘);continue;end;129 xx:=scc[e[i].from];yy:=scc[e[i].go];130 if xx<>yy then write(‘1‘) else write(‘0‘);write(‘ ‘);131 if (xx=x) and (yy=y) then write(‘1‘) else write(‘0‘);132 writeln;133 end;134 end;135 begin136 assign(input,‘input.txt‘);assign(output,‘output.txt‘);137 reset(input);rewrite(output);138 init;139 main;140 close(input);close(output);141 end.