This documentation is automatically generated by online-judge-tools/verification-helper
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_6_A"
#include "../data_structure/FordFullkerson.hpp"
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
ll U,V;cin>>U>>V;
FordFulkerson<ll> g(U);
for(ll i=0;i<V;i++) {
ll u,v,c;cin>>u>>v>>c;
g.add_edge(u,v,c);
}
cout<<g.max_flow(0,U-1)<<endl;
}
#line 1 "test/FordFullkerson.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_6_A"
#line 2 "data_structure/FordFullkerson.hpp"
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
template< typename flow_t >
struct FordFulkerson {
struct edge {
int to;
flow_t cap;
int rev;
bool isrev;
int idx;
};
vector< vector< edge > > graph;
vector< int > used;
const flow_t INF;
int timestamp;
FordFulkerson(int n) : INF(numeric_limits< flow_t >::max()), timestamp(0) {
graph.resize(n);
used.assign(n, -1);
}
void add_edge(int from, int to, flow_t cap, int idx = -1) {
graph[from].emplace_back((edge) {to, cap, (int) graph[to].size(), false, idx});
graph[to].emplace_back((edge) {from, 0, (int) graph[from].size() - 1, true, idx});
}
flow_t dfs(int idx, const int t, flow_t flow) {
if(idx == t) return flow;
used[idx] = timestamp;
for(auto &e : graph[idx]) {
if(e.cap > 0 && used[e.to] != timestamp) {
flow_t d = dfs(e.to, t, min(flow, e.cap));
if(d > 0) {
e.cap -= d;
graph[e.to][e.rev].cap += d;
return d;
}
}
}
return 0;
}
flow_t max_flow(int s, int t) {
flow_t flow = 0;
for(flow_t f; (f = dfs(s, t, INF)) > 0; timestamp++) {
flow += f;
}
return flow;
}
void output() {
for(int i = 0; i < graph.size(); i++) {
for(auto &e : graph[i]) {
if(e.isrev) continue;
auto &rev_e = graph[e.to][e.rev];
cout << i << "->" << e.to << " (flow: " << rev_e.cap << "/" << e.cap + rev_e.cap << ")" << endl;
}
}
}
};
#line 4 "test/FordFullkerson.test.cpp"
#line 6 "test/FordFullkerson.test.cpp"
using namespace std;
using ll=long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
ll U,V;cin>>U>>V;
FordFulkerson<ll> g(U);
for(ll i=0;i<V;i++) {
ll u,v,c;cin>>u>>v>>c;
g.add_edge(u,v,c);
}
cout<<g.max_flow(0,U-1)<<endl;
}