代码如下

include<iostream>

include<cstdio>

include<algorithm>

include<queue>

include<cstring>

using namespace std; const int inf=99999999; const int maxm=100086; const int maxn=10086; int next[maxm],head[maxn],to[maxm],w[maxm],n,m,cnt=-1,cur[maxn],dep[maxn],s,t,j,k,l; inline int HongkongReporter(){ int x=0;char c=getchar(); while (!isdigit(c)){ c=getchar(); } while (isdigit(c)){ x=(x<<3)+(x<<1)+c-48; c=getchar(); }return x; } inline void add(int x,int y,int z){ to[++cnt]=y;next[cnt]=head[x];head[x]=cnt;w[cnt]=z; to[++cnt]=x;next[cnt]=head[y];head[y]=cnt;w[cnt]=0; } bool bfs(){ queue<int> q; memset(dep,0,sizeof(dep)); q.push(s);dep[s]=1; while (!q.empty()){ int u=q.front();q.pop(); for (int i=head[u];i!=-1;i=next[i]){ int v=to[i]; if (w[i]>0&&dep[v]==0){ dep[v]=dep[u]+1; q.push(v); } } } if (dep[t])return 1; else return 0; }

inline int dfs(int x,int dist){ if (x==t)return dist; for (int& i=cur[x];i!=-1;i=next[i]){ int v=to[i]; if (dep[x]+1==dep[v]&&w[i]!=0){ int d=dfs(v,min(dist,w[i])); if (d){ w[i]-=d; w[i^1]+=d; return d; } } } return 0; } int dinic(){ int ans=0; while (bfs()){ for (int i=1;i<=n;i++)cur[i]=head[i]; while (int d=dfs(s,inf))ans+=d; } return ans; } int main(){ n=HongkongReporter();m=HongkongReporter();s=HongkongReporter();t=HongkongReporter(); memset(head,-1,sizeof(head)); memset(next,-1,sizeof(next)); for (int i=1;i<=m;i++){ j=HongkongReporter();k=HongkongReporter();l=HongkongReporter(); if (j==k)continue; add(j,k,l); } printf("%d",dinic()); return 0; }