Cod sursa(job #782031)
#include <fstream>
#include <vector>
#define MAXN 1005
using namespace std;
ifstream f("maxflow.in");
ofstream g("maxflow.out");
int n,m,x,y,z,c[MAXN][MAXN],fx[MAXN][MAXN],back[MAXN],cnt,mn,maxflow;
vector<int> G[MAXN],q;
bool uz[MAXN];
bool BFS();
int main()
{
int i;
f>>n>>m;
for(i=1;i<=m;i++){
f>>x>>y>>z;
G[x].push_back(y);
G[y].push_back(x);
c[x][y]=z;}
uz[1]=1;
back[1]=-1;
while(BFS()){
for(i=0;i<G[n].size();i++){
x=G[n][i];
if(fx[x][n]==c[x][n]||!uz[x])continue;
mn=c[x][n]-fx[x][n];
while(back[x]!=-1){
y=x;
x=back[x];
if(c[x][y]-fx[x][y]<mn)
mn=c[x][y]-fx[x][y];}
if(!mn)continue;
x=G[n][i];
fx[x][n]+=mn;
while(back[x]!=-1){
y=x;
x=back[x];
fx[x][y]+=mn;
fx[y][x]-=mn;}}}
for(i=0;i<G[1].size();i++)
maxflow+=fx[1][G[1][i]];
g<<maxflow<<'\n';
f.close();
g.close();
return 0;
}
bool BFS(){
int i;
for(i=2;i<=n;i++)
uz[i]=0;
cnt=0;
q.clear();
q.push_back(1);
while(cnt<q.size()){
x=q[cnt++];
if(x==n)
continue;
for(i=0;i<G[x].size();i++){
if(!uz[G[x][i]]&&fx[x][G[x][i]]<c[x][G[x][i]]){
q.push_back(G[x][i]);
uz[G[x][i]]=1;
back[G[x][i]]=x;}}}
return uz[n];}