Pagini recente » Cod sursa (job #895098) | Cod sursa (job #270487) | Cod sursa (job #3251045) | Cod sursa (job #780018) | Cod sursa (job #2456742)
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include<queue>
using namespace std;
int cap[1005][1005];
int flow[1005][1005];
vector<int> g[1005];
int parcbfs[1005];
queue<int> q;
bool viz[1005];
bool bfs(int x, int y)
{
int i;
q.push(x);
for(i=1; i<=y; i++)
viz[i]=0;
while(!q.empty()){
int u=q.front();
q.pop();
if(u!=y)
for(i=0; i<g[u].size(); i++){
int v=g[u][i];
if(viz[v]==0 && flow[u][v]<cap[u][v]){
viz[v]=1;
q.push(v);
parcbfs[v]=u;
}
}
}
return viz[y]==1;
}
int main()
{ freopen("maxflow.in", "r",stdin);
freopen("maxflow.out", "w", stdout);
int n,m,i,x,y,z,flu,maxflow=0;
scanf("%d%d", &n, &m);
for(i=1; i<=m; i++){
scanf("%d%d%d", &x, &y, &z);
g[x].push_back(y);
g[y].push_back(x);
cap[x][y]=z;
}
while(bfs(1, n)){
for(i=0; i<g[n].size(); i++){
int v=g[n][i];
if(cap[v][n]>flow[v][n]){
parcbfs[n]=v;
flu=2000000000;
for(int nod=n; nod!=1; nod=parcbfs[nod])
flu=min(flu, cap[parcbfs[nod]][nod]-flow[parcbfs[nod]][nod]);
for(int nod=n; nod!=1; nod=parcbfs[nod]){
flow[parcbfs[nod]][nod]+=flu;
flow[nod][parcbfs[nod]]-=flu;
}
maxflow+=flu;
}
}
}
printf("%d", maxflow);
return 0;
}