【bzoj1797】[Ahoi2009]Mincut 最小割

2015年4月7日5,0486

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

题解

2014.5.26 TAT 写的bfs被叉了。。。

2015.4.7之前的做法存在一些问题,已更正

jcvb:

在残余网络上跑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]。

<==将每个SCC缩成一个点,得到的新图就只含有满流边了。那么新图的任一s-t割都对应原图的某个最小割,从中任取一个把id[u]和id[v]割开的割即可证明。


<==:假设将(u,v)的边权增大,那么残余网络中会出现s->u->v->t的通路,从而能继续增广,于是最大流流量(也就是最小割容量)会增大。这即说明(u,v)是最小割集中必须出现的边。

 

  • dwjshift2015年1月14日 下午11:30 回复

    这个做法似乎有问题0.0……你试试这组数据
    4 4 1 4
    1 2 1
    2 3 1
    2 3 1
    3 4 1

    #1  
    • hzwer2015年4月7日 上午12:52 回复
      admin

      已更正

      #11
  • YZ232015年4月8日 下午6:55 回复

    请问黄学长,这里的残余网络是否包括反向弧?若包含,SCC中的正向满流边的两端点可能会在一个SCC中吗?

    #2  
    • hzwer2015年4月8日 下午8:42 回复
      admin

      残余网络只包含有剩余流量的弧 可能

      #21
  • hzwer2015年12月13日 上午9:32 回复
    admin

    你看下楼下dwjshift的数据

    #3  
    • _浅忆2015年12月13日 上午9:46 回复

      哦…那如果两个中转站之间只有一条路就不用tarjan了?

      #31