首页 > 代码库 > AHOI2009最小割

AHOI2009最小割

1797: [Ahoi2009]Mincut 最小割

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 1072  Solved: 446
[Submit][Status]

Description

A,B两个国家正在交战,其中A国的物资运输网中有N个中转站,M条单向道路。设其中第i (1≤i≤M)条道路连接了vi,ui两个中转站,那么中转站vi可以通过该道路到达ui中转站,如果切断这条道路,需要代价ci。现在B国想找出一个路径切断方案,使中转站s不能到达中转站t,并且切断路径的代价之和最小。 小可可一眼就看出,这是一个求最小割的问题。但爱思考的小可可并不局限于此。现在他对每条单向道路提出两个问题: 问题一:是否存在一个最小代价路径切断方案,其中该道路被切断? 问题二:是否对任何一个最小代价路径切断方案,都有该道路被切断? 现在请你回答这两个问题。

Input

第一行有4个正整数,依次为N,M,s和t。第2行到第(M+1)行每行3个正 整数v,u,c表示v中转站到u中转站之间有单向道路相连,单向道路的起点是v, 终点是u,切断它的代价是c(1≤c≤100000)。 注意:两个中转站之间可能有多条道路直接相连。 同一行相邻两数之间可能有一个或多个空格。

Output

对每条单向边,按输入顺序,依次输出一行,包含两个非0即1的整数,分 别表示对问题一和问题二的回答(其中输出1表示是,输出0表示否)。 同一行相邻两数之间用一个空格隔开,每行开头和末尾没有多余空格。

Sample Input

6 7 1 6
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
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.  
View Code