- Code:
- #include <queue>
- #include <cstdio>
- #include <cstring>
- #include <algorithm>
- using namespace std;
- #define N 100010
- #define M 1000010
- #define inf 1000000000
- int head[N],cur[N],to[M<<1],val[M<<1],nxt[M<<1],idx=1,ans,dis[N],n,m,s,t;
- void add(int a,int b,int c)
- {nxt[++idx]=head[a],to[idx]=b,val[idx]=c,head[a]=idx;}
- bool bfs()
- {
- memset(dis,-1,sizeof dis);
- queue <int> q; q.push(s),dis[s]=0;
- while(!q.empty())
- {
- int p=q.front(); q.pop();
- for(int i=head[p];i;i=nxt[i])
- if(dis[to[i]]==-1&&val[i])
- dis[to[i]]=dis[p]+1,q.push(to[i]);
- } return dis[t]!=-1;
- }
- int dfs(int p,int flow)
- {
- int temp=flow,now;
- if(p==t) return flow;
- for(int i=cur[p];i;i=nxt[i])
- if(val[i]&&dis[to[i]]==dis[p]+1)
- {
- now=dfs(to[i],min(temp,val[i]));
- if(!now) dis[to[i]]==-1;
- val[i]-=now,val[i^1]+=now,temp-=now;
- if(val[i]) cur[p]=i;
- if(!temp) break;
- } return flow-temp;
- }
- void dinic() {while(bfs()) memcpy(cur,head,sizeof cur),ans+=dfs(s,inf);}
- int main()
- {
- scanf("%d%d%d%d",&n,&m,&s,&t);
- for(int i=1,x,y,z;i<=m;i++) scanf("%d%d%d",&x,&y,&z),add(x,y,z),add(y,x,0);
- dinic(),printf("%d\n",ans);
- }
来源: http://www.bubuko.com/infodetail-3012186.html