Prean @ 2021-10-27 16:48:19
RT 1022B的ISAP你喜欢吗
马蜂有些压行请见谅
#include<cstdio>
typedef unsigned ui;
const ui M=205;
ui n,m,s,t,cnt(1),d[M],h[M],cur[M],GAP[M];ui L,R,q[M];
struct Edge{
ui v,nx,flow;
}e[M*50];
inline ui min(const ui&a,const ui&b){
return a>b?b:a;
}
inline void Add(const ui&u,const ui&v,const ui&flow){
e[++cnt]=(Edge){v,h[u],flow};h[u]=cnt;
e[++cnt]=(Edge){u,h[v],0};h[v]=cnt;
}
inline void BFS(){
ui u,v,E;GAP[d[q[L=R=1]=t]=1]=1;
while(L<=R)for(u=q[L++],E=cur[u]=h[u];E;E=e[E].nx)!d[v=e[E].v]&&++GAP[d[q[++R]=v]=d[u]+1];
}
ui ISAP(const ui&u,const ui&flow){
if(u==t)return flow;
ui v,F,used=flow;
for(ui&E=cur[u];E;E=e[E].nx){
if(e[E].flow&&d[v=e[E].v]+1==d[u]){
if(F=ISAP(v,min(flow,e[E].flow)),e[E].flow-=F,e[E^1].flow+=F,!(used-=F))return flow;
}
}
return!--GAP[d[u]]&&(d[s]=n+2),cur[u]=h[u],++GAP[++d[u]],flow-used;
}
signed main(){
ui u,v,flow;long long ans(0);scanf("%u%u%u%u",&n,&m,&s,&t);
while(m--)scanf("%u%u%u",&u,&v,&flow),Add(u,v,flow);
BFS();while(d[s]<=n)ans+=ISAP(s,-114514);printf("%lld",ans);
}
by 金珂拉 @ 2021-10-27 20:26:46
有“些”压行
by Stinger @ 2022-03-11 19:52:17
你刷新了我对ISAP的认知