原题链接：https://www.luogu.org/problem/show?pid=3376

没什么要说的，这只是一个普通的ISAP板子，只不过用我最喜欢的代码风格重写了一遍。

 

#include
     
      #include
      
       #include
       
        #include
        
         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
         

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]

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;}