5797: BZOJ1797：[Ahoi2009]Mincut 最小割

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

输入格式

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

输出格式

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

样例输入

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

样例输出

1 0
1 0
0 0
1 0
0 0
1 0
1 0

提示

设第(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

2015.4.16新加数据一组，可能会卡掉从前可以过的程序。

题目来源

Day1