Cod sursa(job #431616)
#include <stdio.h>
#include <vector>
#define IN "maxflow.in"
#define OUT "maxflow.out"
#define Lg 1001
using namespace std;
vector <long> V[Lg];
long Cost[Lg][Lg];
long T[Lg], n, m, x, y, Q[Lg];
long sf, Flux;
void citire()
{
scanf ("%ld %ld",&n,&m);
for (long i=0;i<m;i++)
{
scanf ("%ld %ld",&x, &y);
V[x].push_back(y);
V[y].push_back(x);
scanf ("%ld",&Cost[x][y]);
}
}
long ok()
{
sf=0;
for (long i=1;i<=n;i++)
T[i]=0;
T[1]=-1;
Q[sf++]=1;
for (long i=0;i<sf;i++)
for (long k=0;k<V[Q[i]].size();k++)
{
if (T[V[Q[i]][k]] || Cost[Q[i]][V[Q[i]][k]]==0)
continue;
T[V[Q[i]][k]]=Q[i];
Q[sf++]=V[Q[i]][k];
if (V[Q[i]][k]==n)
return 1;
}
return 0;
}
void solve()
{
long fl,nod;
while (ok())
{
for (long i=1;i<n;i++)
{
if (!T[i] || !Cost[i][n])
continue;
fl=Cost[i][n];
nod=i;
while (nod!=1)
{
fl=min(fl,Cost[T[nod]][nod]);
nod=T[nod];
}
if (!fl)
continue;
Cost[i][n]-=fl;
Cost[n][i]+=fl;
nod=i;
while (nod!=1)
{
Cost[T[nod]][nod]-=fl;
Cost[nod][T[nod]]+=fl;
nod=T[nod];
}
Flux+=fl;
}
}
printf("%ld\n",Flux);
}
int main ()
{
freopen (IN ,"r", stdin);
freopen (OUT ,"w", stdout);
citire();
solve();
return 0;
}