Pagini recente » Cod sursa (job #2045241) | Cod sursa (job #1791517) | Cod sursa (job #1900500) | Cod sursa (job #985576) | Cod sursa (job #2112481)
#include <fstream>
#include <vector>
#include <queue>
#include <string.h>
#define INF 1000000000
using namespace std;
ifstream fi("maxflow.in");
ofstream g("maxflow.out");
queue <int> q;
queue <int> vn;
vector <int> v[1001];
int c[1001][1001],f[1001][1001],t[1001],viz[1001],n;
void BFS(int i)
{
int nod,vec;
t[i]=-1;
viz[i]=1;
q.push(i);
while(!q.empty())
{
nod=q.front();
q.pop();
for(i=0;i<v[nod].size();i++)
{
vec=v[nod][i];
if(viz[vec]==0 && c[nod][vec]-f[nod][vec]>0)
{
if(vec!=n)
{
t[vec]=nod;
viz[vec]=1;
q.push(vec);
}
else
{
vn.push(nod);
}
}
}
}
}
int main()
{
int rez=0,m,i,x,y,flux;
fi>>n>>m;
for(i=1;i<=m;i++)
{
fi>>x>>y>>flux;
c[x][y]+=flux;
v[x].push_back(y);
v[y].push_back(x);
}
while(1)
{
memset(viz,0,sizeof(viz));
memset(t,0,sizeof(t));
BFS(1);
if(vn.empty())
break;
while(!vn.empty())
{
t[n]=vn.front();
vn.pop();
flux=INF;
x=n;
while(x!=1)
{
flux=min(c[t[x]][x]-f[t[x]][x],flux);
x=t[x];
}
x=n;
rez+=flux;
while(x!=1)
{
f[t[x]][x]+=flux;
f[x][t[x]]-=flux;
x=t[x];
}
}
}
g<<rez;
return 0;
}