One of Pang’s research interests is the maximum flow problem.
A directed graph G with n vertices is universe if the following condition is satisfied:
G is the union of k vertex-independent simple paths from vertex 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 graph with n vertices and 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?
Input
The first line contains two integers n and m (2≤n≤100000,1≤m≤200000).
Each of the next 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
Output a single integer — the minimum number of operations.
Examples
Input
4 3
1 2 1
2 3 2
3 4 3
Output
1
Input
4 4
1 2 1
1 3 1
2 4 2
3 4 2
Output
1
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long LL;
const int N = 4e5 + 10;
int h[N], cnt = 0, n, m;
int x, y, w;
vector<int> ma[N];
struct node {
int y, w, ne;
} s[N];
bool vis[N];
priority_queue<pair<LL, LL> > q;
pair<LL, LL> t;
void add(int x, int y, int w) {
s[++cnt].y = y;
s[cnt].w = w;
s[cnt].ne = h[x];
h[x] = cnt;
}
void dfs(int x, int l) {
for (int i = h[x]; i; i = s[i].ne) {
int y = s[i].y;
int w = s[i].w;
ma[l].push_back(w);
if (y != n)
dfs(y, l);
else {
vis[l] = 1;
return;
}
}
}
signed main() {
ios::sync_with_stdio(0);
cin >> n >> m;
LL sum = 0;
while (m--) {
cin >> x >> y >> w;
add(x, y, w);
sum += w;
}
int l = 0;
for (int i = h[1]; i; i = s[i].ne) {
int y = s[i].y;
int w = s[i].w;
ma[l].push_back(w);
dfs(y, l++);
}
int len = inf;
for (int i = 0; i < l; i++) {
if (vis[i] == 0) continue;
if (len > ma[i].size()) len = ma[i].size();
}
LL d = sum / len;
LL now = 0;
LL ans = 0;
for (int i = 0; i < l; i++) {
if (vis[i] == 0) continue;
if (ma[i].size() != len) continue;
sort(ma[i].begin(), ma[i].end());
now += ma[i][0];
int x = ma[i][0];
for (int j = 1; j < len; j++) {
if (ma[i][j] != x) {
q.push({-j, ma[i][j] - x});
x = ma[i][j];
}
}
}
while (now < d && q.size()) {
t = q.top();
q.pop();
if (now + t.second < d) {
now += t.second;
ans -= t.first * t.second;
} else {
ans -= (t.first) * (d - now);
break;
}
}
cout << ans << "\n";
return 0;
}