原题链接：https://www.luogu.org/problem/show?pid=3376
没什么要说的，这只是一个普通的ISAP板子，只不过用我最喜欢的代码风格重写了一遍。
#include<cstdio> #include<iostream> #include<cstring> #include<queue> using namespace std; void read(int &y) { y=0;char x=getchar(); while(x<'0'||x>'9') x=getchar(); while(x>='0'&&x<='9') { y=y*10+x-'0'; x=getchar(); } } int min(int x,int y) { if(x<y) return x; else return y; } struct edge { int u,v,flow,cap; }e[200005]; int n,m,s,t,cnt; int nxt[200005],f[200005]; int d[10005],par[10005],num[10005],cur[10005],vis[10005]; void add(int x,int y,int z) { e[++cnt].u=x;e[cnt].v=y;e[cnt].cap=z;e[cnt].flow=0; nxt[cnt]=f[x];f[x]=cnt; e[++cnt].u=y;e[cnt].v=x;e[cnt].cap=0;e[cnt].flow=0; nxt[cnt]=f[y];f[y]=cnt; } void bfs() { queue<int>q; vis[t]=1; q.push(t); while(!q.empty()) { int k=q.front(); q.pop(); for(int i=f[k];i;i=nxt[i]) { if(vis[e[i].v]==0&&e[i].cap==0) { vis[e[i].v]=1; d[e[i].v]=d[k]+1; q.push(e[i].v); } } } } int agument() { int p=t,ans=2147483647; while(p!=s) { ans=min(ans,e[par[p]].cap-e[par[p]].flow); p=e[par[p]].u; } p=t; while(p!=s) { e[par[p]].flow+=ans; e[par[p]^1].flow-=ans; p=e[par[p]].u; } return ans; } int isap() { int sf=0,p=s; for(int i=1;i<=n;i++) { num[d[i]]++; cur[i]=f[i]; } while(d[s]<n) { if(p==t) { sf+=agument(); p=s; } int flag=0; for(int i=cur[p];i;i=nxt[i]) { if(e[i].cap>e[i].flow&&d[p]==d[e[i].v]+1) { flag=1; par[e[i].v]=i; cur[p]=i; p=e[i].v; break; } } if(flag==0) { if(--num[d[p]]==0) break; int mn=n-1; for(int i=f[p];i;i=nxt[i]) { if(e[i].cap>e[i].flow) mn=min(mn,d[e[i].v]); } d[p]=mn+1; num[d[p]]++; cur[p]=f[p]; if(p!=s) p=e[par[p]].u; } } return sf; } int main() { read(n);read(m);read(s);read(t); cnt++; for(int i=1;i<=m;i++) { int a,b,c; read(a);read(b);read(c); add(a,b,c); } bfs(); int ans=isap(); printf("%d",ans); return 0; }