#P16986. [SGU457] Snow in Berland

[SGU457] Snow in Berland

题目描述

Berland 的冬天总是大雪纷飞。首都有 nn 个路口和 mm 条单向道路。第 ii 条道路从路口 xix_i 指向路口 yiy_i,道路上有 wiw_i 吨积雪。

政府雇佣了公司 Snow White 清理积雪。公司每天派出一辆清雪车:

  • 清雪车从路口 AA 出发;
  • 沿道路方向行驶,最终到达路口 BB 并结束当天工作;
  • 一天的路线可以重复经过同一条道路,也可以重复经过任意路口,包括 AA 和 BB;
  • 每经过一条道路一次,就清除该道路 11 吨积雪;
  • 如果某条道路已经没有积雪,则清雪车不能再经过这条道路。

部分道路具有历史价值,称为历史道路。所有历史道路都必须被完全清理,即最终这些道路的积雪必须变成 00。普通道路则不要求清空。

**本改编版附加保证:**忽略道路方向后,仅沿积雪量 大于 00 的历史道路,可以从 AA 到达每一条积雪量大于 00 的历史道路的两个端点。积雪量为 00 的历史道路无需清理,不受这一保证约束。

政府按工作天数向 Snow White 支付费用,因此公司希望在满足上述要求的前提下,工作的天数尽可能多。

在所有满足以下要求的工作安排中,求公司最多能够工作多少天:

  1. 每天清雪车从 AA 出发并最终到达 BB;
  2. 每次经过道路时该道路仍有至少 11 吨积雪;
  3. 所有历史道路最终必须被完全清空。

只需要输出最大工作天数,不需要输出每天的具体路线。

输入格式

第一行包含四个整数 n,m,A,Bn,m,A,B:

  • 2≤n≤1002\le n\le100;
  • 0≤m≤50000\le m\le5000;
  • 1≤A,B≤n1\le A,B\le n;
  • A≠BA\ne B。

接下来 mm 行,每行四个整数 xi,yi,wi,tix_i,y_i,w_i,t_i,表示一条从 xix_i 指向 yiy_i 的单向道路:

  • 1≤xi,yi≤n1\le x_i,y_i\le n,且 xi≠yix_i\ne y_i;
  • 0≤wi≤1000\le w_i\le100,表示道路上的积雪吨数;
  • ti∈{0,1}t_i\in\{0,1\};
    • ti=0t_i=0 表示普通道路;
    • ti=1t_i=1 表示历史道路。

同一方向的两个路口之间至多有一条道路。

**保证:**将所有 ti=1t_i=1 且 wi>0w_i>0 的道路视为无向边后,所有这些道路的端点都与 AA 连通。若不存在积雪量大于 00 的历史道路,则此条件自然成立。

输出格式

输出一个整数 pp,表示能够工作的最大天数。

如果不存在满足历史道路清理要求的工作安排,输出 00。

样例 1

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

3 3 1 2
1 3 2 0
3 2 3 0
1 2 1 0
3