Extra
Time
[AHOI2009] 最小截断——胡策day3 Time:0.9s Memory:50M AC:34% Submit:3

【题目描述】

 

宇宙旅行总是出现一些意想不到的问题,这次小可可所驾驶的宇宙飞船所停的空间站发生了故障,这个宇宙空间站非常大,它由N个子站组成,子站之间有M条单向通道,假设其中第i(1<=i<=M)条单向通道连接了xi,yi两个中转站,那么xi子站可以通过这个通道到达yi子站,如果截断这条通道,需要代价ci。现在为了将故障的代价控制到最小,小可可必须想出一个截断方案,使a站不能到达b子站,并且截断的代价之和最小。我们称之为最小截断,小可可很快解决了这个故障,但是爱思考的小可可并不局限于此,为了今后更方便的解决同类故障,他考虑对每条单向通道:

1,是否存在一个最小代价路径截断方案,其中该通道被切断?

2,是否对任何一个最小代价路径切断方案,都有该通道被切断?

聪明的你能帮小可可解决他的疑问吗?

 

【输入格式】

 

第一行有4个整数,依次为N,M,a和b;

第二行到第(m+1)行每行3个正整数x,y,c表示x子站到y子站之间有单向通道相连,单向通道的起点是x终点是y,切断它的代价是c(1<=c<=10000);

两个子站之间可能有多条通道直接连接。

 

【输出格式】

对每一个单向通道,按输入的顺序,依次输出一行包含两个非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

【提示】

 

提示:100%的数据中,N<=4000,M<=60000

  70%的数据中,N<=1000,M<=40000

  40%的数据中,N<=200,M<=2000

 

【来源】

AHOI2009