FASTFLOW - Fast Maximum Flow

Given a graph with N (2 ≤ N ≤ 5,000) vertices numbered 1 to N and M (1 ≤ M ≤ 30,000) undirected, weighted edges, compute the maximum flow / minimum cut from vertex 1 to vertex N.

Input

The first line contains the two integers N and M. The next M lines each contain three integers A, B, and C, denoting that there is an edge of capacity C (1 ≤ C ≤ 109) between nodes A and B (1 ≤ A, B ≤ N). Note that it is possible for there to be duplicate edges, as well as an edge from a node to itself.

Output

Print a single integer (which may not fit into a 32-bit integer) denoting the maximum flow / minimum cut between 1 and N.

Example

```Input:
4 6
1 2 3
2 3 4
3 1 2
2 2 5
3 4 3
4 3 3

Output:
5```

Code Examples

#1 Code Example with C++ Programming

```Code - C++ Programming```

``````#include <bits/stdc++.h>

typedef long long ll;
using namespace std;

#define GC getchar_unlocked()
int scan()
{
int ret=0,sign=1;
int ip=GC;
for(;ip<'0'||ip>'9';ip=GC);
for(;ip>='0'&&ip<='9';ip=GC)
ret=ret*10+ip-'0';
return (ret*sign);
}

const int maxnodes = 5010;
const int _INF = 1000000000;
int nodes, src, dest;
int dist[maxnodes], work[maxnodes];

struct Edge {
int to, rev;
int f, cap;
};

vector<Edge> g[maxnodes];

void addEdge(int s, int t, int cap){
Edge a = {t, (int)g[t].size(), 0, cap};
Edge b = {s, (int)g[s].size(), 0, cap};
g[s].push_back(a);
g[t].push_back(b);
}

bool dinic_bfs() {
fill(dist, dist + nodes, -1);
dist[src] = 0;
queue<int> Q;
Q.push(src);
while(!Q.empty())
{
int u = Q.front();
Q.pop();
for (int j = 0; j < (int) g[u].size(); j++) {
Edge &e = g[u][j];
int v = e.to;
if (dist[v] < 0 && e.f < e.cap) {
dist[v] = dist[u] + 1;
Q.push(v);
}
}
}
return dist[dest] >= 0;
}

int dinic_dfs(int u, int f) {
if (u == dest)
return f;
for (int &i = work[u]; i < (int) g[u].size(); i++) {
Edge &e = g[u][i];
if (e.cap <= e.f) continue;
int v = e.to;
if (dist[v] == dist[u] + 1) {
int df = dinic_dfs(v, min(f, e.cap - e.f));
if (df > 0) {
e.f += df;
g[v][e.rev].f -= df;
return df;
}
}
}
return 0;
}

ll maxFlow(int _src, int _dest) {
src = _src;
dest = _dest;
ll result = 0;
int delta = 0;
while (dinic_bfs()) {
fill(work, work + nodes, 0);
while ((delta = dinic_dfs(src, _INF)))
result += delta;
}
return result;
}

int main()
{

int m,u,v,c;
nodes=scan();
m=scan();
while(m--)
{
u=scan();
v=scan();
--u,--v;
c=scan();
}
cout<<maxFlow(0,nodes-1)<<"\n";
return 0;
}``````
Copy The Code &

Input

cmd
4 6
1 2 3
2 3 4
3 1 2
2 2 5
3 4 3
4 3 3

Output

cmd
5