Pagini recente » Cod sursa (job #1115536) | Cod sursa (job #683449) | Cod sursa (job #242006) | Cod sursa (job #3253884) | Cod sursa (job #1745447)
#include<bits/stdc++.h>
using namespace std;
struct Edge {
int x,y,flow;
};
const int INF=1e9+69*69*69;
int x,y,z,n,m,d[1005],ptr[1005];
vector<Edge> E;
vector<int> lde[1005];
void add_Edge(int x,int y,int flow) {
Edge e1={x,y,flow};
Edge e2={y,x,0};
lde[x].push_back((int)E.size());
E.push_back(e1);
lde[y].push_back((int)E.size());
E.push_back(e2);
}
bool bfs() {
int qh,qt,q[1005],to;
memset(d,~0,sizeof(d));
d[1]=0; q[1]=1;
for(qh=qt=1;qh<=qt && d[n]==-1;++qh)
for(auto id:lde[q[qh]])
{
to=E[id].y;
if(d[to]==-1 && E[id].flow>0) q[++qt]=to,d[to]=d[q[qh]]+1;
}
return d[n]!=-1;
}
int dfs(int x,int flow) {
if(!flow) return 0;
if(x==n) return flow;
for(;ptr[x]<(int)lde[x].size();++ptr[x])
{
int id=lde[x][ptr[x]],to=E[id].y;
if(d[to]!=d[x]+1) continue;
int pushed=dfs(to,min(flow,E[id].flow));
if(pushed)
{
E[id].flow-=pushed;
E[id^1].flow+=pushed;
return pushed;
}
}
return 0;
}
int Dinic() {
int flow,ans=0;
while(bfs())
{
memset(ptr,0,sizeof(ptr));
while((flow=dfs(1,INF))) ans+=flow;
}
return ans;
}
int main()
{
ifstream cin("maxflow.in");
ofstream cout("maxflow.out");
ios_base::sync_with_stdio(0);
for(cin>>n>>m;m;--m) cin>>x>>y>>z,add_Edge(x,y,z);
cout<<Dinic()<<'\n';
return 0;
}