求助ISAP

P3376 【模板】网络最大流

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的认知


|