BZPRO
#3789. 扫雪车
内存限制：64 MiB
时间限制：10 Sec
提交
提交记录
讨论
题目描述
n个城市和m条单向道路构成一个有向图，每条道路e上有整数积雪量We。一辆扫雪车每天从城市s开到t，经过一条道路一次就将其雪量减1（不能走雪量为0的道路）。有些道路（称为重要道路）必须清空积雪，这些道路的导出子图是包含s的弱连通图。求扫雪车工作天数的最大值。或判断无解。
弱连通图：将有向图的所有的有向边替换为无向边，所得到的图称为原图的基图。如果一个有向图的基图是连通图，则有向图是弱连通图。
输入格式
第一行四个数n，m，s，t。
下面m行，每行四个数x，y，w，t。表示这条道路连接的两个城市，积雪量，和道路种类。若t为0则是普通道理，t为1则是重要道路。
输出格式
扫雪车工作天数的最大值。或判断无解，输出0。
样例
样例输入
4 7 1 4
1 2 3 1
2 1 100 0
2 4 1 0
1 3 1 0
3 4 4 0
2 3 2 1
1 4 2 0
样例输出
6
数据范围与提示
2 ≤ n ≤ 100; 0 ≤ m ≤ 5000; 1 ≤ s,t ≤ n; s ≠ t
1 ≤ xi,yi ≤ n; xi ≠ yi; 0 ≤ wi ≤ 100; 0 ≤ ti ≤ 1
BZPRO