One of Pang \textit{Pang}Pang research interests is the maximum flow problem.
A directed graph G {G}G with n {n}n vertices is universe \textit{universe}universe if the following condition is satisfied:
G {G}G is the union of k {k}k vertex-independent simple paths from vertex 1 {1}1 to vertex n of the same length.
A set of paths is vertex-independent if they do not have any internal vertex in common.
A vertex in a path is called internal if it is not an endpoint of that path.
A path is simple if its vertices are distinct.
Let G be a universe \textit{universe}universe graph with n {n}n vertices and m {m}m edges. Each edge has a non-negative integral capacity. You are allowed to perform the following operation any (including 0 times to make the maximum flow from vertex 1 to vertex n as large as possible:
Let e be an edge with positive capacity. Reduce the capacity of e by 1 and increase the capacity of another edge by 1 .
Pang wants to know what is the minimum number of operations to achieve it?
输入描述:
The first line contains two integers n and m ( 2 ≤ n ≤ 100000 , 1 ≤ m ≤ 200000 ) .
Each of the next m {m}m lines contains three integers x , y and z , denoting an edge from x to y with capacity z ( 1 ≤ x , y ≤ n , 0 ≤ z ≤ 1000000000 )
It’s guaranteed that the input is a universe graph without multiple edges and self-loops.
输出描述:
Output a single integer — the minimum number of operations.
输入1
4 3 1 2 1 2 3 2 3 4 3
输出1
1
输入2
4 4 1 2 1 1 3 1 2 4 2 3 4 2
输出2
2
题意：
给定一个有向图，n个点，m条边
在这个图中，任意两条路径中没有公共点（除了两个端点之外）
而且在路径上，点是不会经过两次的
每条路径的长度相等
保证没有重边和自环
这m条边的容量都是≥ 0 的，在某一条便的容量> 0 的时候，可以进行若干次操作（也可以为0，即不进行操作）：{
选择一条容量大于0的边，将他的容量-1，然后选择一条其他的边，让这条边的容量+1
}
问在图中的最大流尽可能大的情况下，最少的操作步数是多少？
思路：
首先将所有的输入的容量相加，然后将图分解成若干个路径，将题目中说的union进行分解，然后保存在vector中，对于每一条路径，我们记录他们的容量，然后将每一条路径上的容量值排序（从小到大）
在这里，我们就已经能够获取每一条路径的长度，然后定义一个limit值让他等于每一段的平均值
然后统计每一段上的容量之和sum，如果容量之和小于定义的limit，就需要对它进行操作，反之不需要操作
而操作的次数就是 sum−limit，肯定是从容量大的调整到容量小的上面
struct node { int u, to, nex; ll flow; }e[maxn << 1]; int n, m; int idx, head[maxn]; void init() { idx = 0; for (int i = 0; i <= n; i++) head[i] = -1; } void add(int u, int v, ll w) { e[idx].u = u; e[idx].to = v; e[idx].flow = w; e[idx].nex = head[u]; head[u] = idx++; } vector<ll> edges[maxn]; void dfs(int u, int id) { if (u == n) return; for (int i = head[u]; ~i; i = e[i].nex) { edges[id].push_back(e[i].flow); dfs(e[i].to, id); } } int main() { n = read, m = read; init(); ll sum = 0; for (int i = 1; i <= m; i++) { int u = read, v = read; ll flow = read; sum += flow; add(u, v, flow); } int t = 0; for (int i = head[1]; ~i; i = e[i].nex) { edges[++t].push_back(e[i].flow); dfs(e[i].to, t); } //length of each of edge is same //cout << t << endl; /* for (int i = 1; i <= t; i++) { for (int j = 0; j < edges[i].size(); j++) { cout << edges[i][j] << ' '; } puts(""); } */ for (int i = 1; i <= t; i++) { sort(edges[i].begin(), edges[i].end()); } ll ans = 0LL; //debug(sum); //debug(edges[1].size()); ll lim = sum / edges[1].size(); //debug(sum); //debug(edges[1].size()); assert(sum % edges[1].size() == 0); //cout << lim << endl; /* for (int i = 1; i <= t; i++) { sort(edges[i].begin(), edges[i].end()); ll curFlow = 0LL; int flag = 0; int siz = edges[i].size(); for (int j = 0; j < siz; j++) { curFlow += edges[i][j]; if (curFlow >= lim) { flag = 1; break; } } if (flag) break; ans += lim - curFlow; } */ // pull flow steps for (int ii = 1; ii <= edges[1].size(); ii++) { ll curFlow = 0LL; int flag = 0; int i = ii - 1; for (int p = 1; p <= t; p++) { curFlow += edges[p][i]; if (curFlow >= lim) { flag = 1; break; } } if (!flag) ans += lim - curFlow; } cout << ans << endl; return 0; } /** 4 3 1 2 1 2 3 2 3 4 3 -> 1 4 4 1 2 1 1 3 1 2 4 2 3 4 2 -> 1 **/
文章知识点与官方知识档案匹配，可进一步学习相关知识
算法技能树leetcode-贪心122-买卖股票的最佳时机 II8226 人正在系统学习中
