最小割
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≤105)。
注意:两个中转站之间可能有多条道路直接相连。 同一行相邻两数之间可能有一个或多个空格。
其中, N≤4000,M≤60000。
对每条单向边,按输入顺序,依次输出一行,包含两个非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