题面传送门
直接上
板子即可，注意加几个剪枝，跑得飞快。
代码实现:
#include<cstdio>
#include<cstring>
#include<queue>
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
int n,m,k,x,y,z,d[1039],now[1039],st,t,nows,cur;
long long ans;
struct yyy{int to,w,z;}tmp;
struct ljb{int head,h[1039];yyy f[10039];inline void add(int x,int y,int z){f[head]=(yyy){y,z,h[x]};h[x]=head++;}
}s;
queue<int > q;
inline int bfs(){while(!q.empty()) q.pop();memset(d,0x3f,sizeof(d));q.push(st);d[st]=0;now[st]=s.h[st];while(!q.empty()){nows=q.front();q.pop();cur=s.h[nows];while(cur!=-1){tmp=s.f[cur];if(tmp.w&&d[tmp.to]>=1e9) {d[tmp.to]=d[nows]+1;now[tmp.to]=s.h[tmp.to];q.push(tmp.to);if(tmp.to==t) return 1;}cur=tmp.z;}}return 0;
}
inline long long dfs(int x,long long sum){if(x==t) return sum;long long k,pus=0;int cur=now[x];yyy tmp;while(cur!=-1){tmp=s.f[cur];now[x]=cur;if(d[tmp.to]==d[x]+1&&tmp.w){k=dfs(tmp.to,min(tmp.w,sum));if(!k) d[tmp.to]=1e9;s.f[cur].w-=k;s.f[cur^1].w+=k;pus+=k;sum-=k;}if(!sum) break;cur=tmp.z;}return pus;
}
int main(){//freopen("1.in","r",stdin);register int i;memset(s.h,-1,sizeof(s.h));scanf("%d%d",&m,&n);st=1;t=n;for(i=1;i<=m;i++) scanf("%d%d%d",&x,&y,&z),s.add(x,y,z),s.add(y,x,0);while(bfs())ans+=dfs(st,1e15);printf("%lld\n",ans);
}