PID524 / [AHOI2009]最小截断
题目描述

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

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

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

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

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

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

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

输入格式

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

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

输出格式

对每一个单向通道,按输入的顺序,依次输出一行包含两个非0即1的整数,分别表示对问题一和问题二的回答(其中1表示是,0表示否)。每行两个整数之间用一个空格分隔开。

样例输入
样例输出
提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论