#P3789. 扫雪车
扫雪车
题目描述
个城市和 条单向道路构成一个有向图,每条道路 上有整数积雪量 。一辆扫雪车每天从城市 开到 ,经过一条道路一次就将其雪量减 (不能走雪量为 的道路)。有些道路(称为重要道路)必须清空积雪,这些道路的导出子图是包含 的弱连通图。求扫雪车工作天数的最大值,或判断无解。
弱连通图:将有向图的所有的有向边替换为无向边,所得到的图称为原图的基图。如果一个有向图的基图是连通图,则有向图是弱连通图。
输入格式
第一行四个数 。
下面 行,每行四个数 。表示这条道路连接的两个城市,积雪量,和道路种类。若 为 则是普通道路, 为 则是重要道路。
输出格式
扫雪车工作天数的最大值。或判断无解,输出 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
数据规模与约定
对于 的数据,,,,,,,,。
本站评测另保证以下可行性条件。设每条道路的使用次数是不超过其积雪量的非负整数,重要道路的使用次数恰等于其积雪量。除 外每个城市的进入和离开次数相等, 的净离开次数等于 的净进入次数且为非负。在所有这样的分配中,如果最大的净离开次数为正,则至少有一种取得最大值的分配,其使用次数为正的道路忽略方向后都与 连通。这里可以使用普通道路维持连通,初始积雪量为 的道路不能通行。此条件由本站全部 10 组评测数据的最大流见证核验。