#P3789. 扫雪车

    ID: 2992 传统题 1000ms 64MiB 尝试: 79 已通过: 28 难度: 7 上传者: 标签>CF2200提高+/省选-上下界最大流下界转化超级源汇Dinic残量网络欧拉回路

扫雪车

题目描述

nn 个城市和 mm 条单向道路构成一个有向图,每条道路 ee 上有整数积雪量 wew_e。一辆扫雪车每天从城市 ss 开到 tt,经过一条道路一次就将其雪量减 11(不能走雪量为 00 的道路)。有些道路(称为重要道路)必须清空积雪,这些道路的导出子图是包含 ss 的弱连通图。求扫雪车工作天数的最大值,或判断无解。

弱连通图:将有向图的所有的有向边替换为无向边,所得到的图称为原图的基图。如果一个有向图的基图是连通图,则有向图是弱连通图。

输入格式

第一行四个数 n,m,s,tn,m,s,t。

下面 mm 行,每行四个数 x,y,w,tx,y,w,t。表示这条道路连接的两个城市,积雪量,和道路种类。若 tt 为 00 则是普通道路,tt 为 11 则是重要道路。

输出格式

扫雪车工作天数的最大值。或判断无解,输出 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

数据规模与约定

对于 100%100\% 的数据,2≤n≤1002 \le n \le 100,0≤m≤5×1030 \le m \le 5 \times 10^3,1≤s,t≤n1 \le s,t \le n,s≠ts \ne t,1≤xi,yi≤n1 \le x_i,y_i \le n,xi≠yix_i \ne y_i,0≤wi≤1000 \le w_i \le 100,0≤ti≤10 \le t_i \le 1。

本站评测另保证以下可行性条件。设每条道路的使用次数是不超过其积雪量的非负整数,重要道路的使用次数恰等于其积雪量。除 s,ts,t 外每个城市的进入和离开次数相等,ss 的净离开次数等于 tt 的净进入次数且为非负。在所有这样的分配中,如果最大的净离开次数为正,则至少有一种取得最大值的分配,其使用次数为正的道路忽略方向后都与 ss 连通。这里可以使用普通道路维持连通,初始积雪量为 00 的道路不能通行。此条件由本站全部 10 组评测数据的最大流见证核验。