在 MSU 网络机械系法官入学考试中,Sasha 遇到了有关 Ford-Fulkerson 算法的问题。他非常了解这个话题,因为他在编程比赛中多次涉及到这个话题。作为该问题的任务,他获得了一个具有部分构建流程的网络,他必须使用该网络来演示算法的工作流程。他很快就写完了文字,看了一眼题目,才发现给定的网络是错误的!
假设给你一个有向图 G(V, E),其中有两个特殊节点 s 和 t,称为源节点和汇节点。我们将图中的节点数表示为 n,即 n = |V| m代表图中有向边的数量,即m = |E|。出于此问题的目的,我们始终将节点 1 视为源,节点 n 视为汇。此外,对于图 e 的每条边,我们定义容量函数 c(e) 和流量函数 f(e)。如果满足以下条件,函数 f(e) 表示正确的流程:
1. 对于每条边 $$e \in E$$,流量为非负且不超过容量 c(e),即 0 ≤ f(e) ≤ c(e)。
2. 对于每个节点 $$v \in V$$,即不是源节点也不是汇点(v ≠ s 和 v ≠ t),进入 v 的所有边的流量之和等于从 v 出去的所有边的流量之和。换句话说,v 中不存在流量滞留。
很明显,由于昨晚准备了考试,作业中存在很多错误。萨莎要求一位教授修复网络或给出正确的任务,但得到的答复是治安学生应该能够自己修复网络。由于教授不希望任务变得更容易,他要求 Sasha 以尽可能减少更改总数的方式修复网络。 Sasha 不允许删除边、添加新边或反转现有边的方向。他唯一能做的就是改变容量函数c(e)和流量函数f(e)。此外,所有值都应保持非负整数。在任何意义上都不要求流量达到最大值。
求 Sasha 为了使流程正确而必须对函数 f(e) 和 c(e) 进行的最小可能总变化。总变化定义为绝对差值之和,即如果新函数为 f * (e) 和 c * (e),则总变化为 $$\sum_{e \in E} |f(e) - f^*(e)| + |c(e) - c^*(e)|$$。
输入
输入的第一行包含两个整数 n 和 m (2 ≤ n ≤ 100, 0 ≤ m ≤ 100) - 分别是图中的节点数和边数。接下来的 m 行每行包含边的描述,由四个整数 ui、vi、ci 和 fi (1 ≤ ui, vi ≤ n, ui ≠ vi, 0 ≤ ci, fi ≤ 1 000 000) 组成——边起始节点的索引、边到达的节点的索引、当前容量和流量值。
节点号 1 是源,节点号 n 是汇点。确保没有边到达源,也没有边从接收器开始。
给定图不包含自环,但可能包含多个边。
输出
打印一个整数——Sasha 为获得正确的流程描述而必须执行的更改的最小总和。
示例
输入 #1
2 1 1 2 2 1
输出 #1
0
输入 #2
2 1 1 2 1 2
输出 #2
1
输入 #3
3 3 1 2 1 1 2 3 2 2 1 3 3 3
输出 #3
1
输入#4
4 2 2 3 1 1 3 2 1 1
输出#4
0
注意
在第一个示例中,流量最初是正确的。请注意,流量不是最大,但这不是必需的。
在第二个示例中,唯一边缘的流量值大于其容量。有两种方法可以解决此问题:将容量增加到 2 或将流量减少到 1。
在第三个示例中,只有 1 个单位的流量到达顶点 2,但有 2 个单位从顶点 2 流出。可能的解决方案之一是将第二条边上的流量值减少 1。
在第四个示例中,存在孤立的流量循环,但根据定义,此描述是正确的。