P3376 【模板】网络最大流

Ayaka_Li @ 2023-08-08 16:52:55

为什么ISAP不跑bfs也能AC a

#include <iostream>
#include <queue>
#include <cstring>
#define int long long
using namespace std;
const int INF=0x7fffffff;
const int N=1e6+10;
struct edge {
    int v,nxt,val;
}e[N];
int head[N],cnt=1;//!!!!!!!
inline void add(int u,int v,int w) {
    e[++cnt].v=v;
    e[cnt].val=w;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
int n,m,s,t;
int dep[N],gap[N];
int M_flow;
int dfs(int u,int flow) {
    if (u==t) {
        M_flow+=flow;
        return flow;
    }
    int used=0;
    for (int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if (e[i].val&&dep[v]+1==dep[u]) {
            int mi=dfs(v,min(e[i].val,flow-used));
            if (mi) {
                e[i].val-=mi;
                e[i^1].val+=mi;
                used+=mi; 
            }
            if (used==flow)
                return used;
        }
    }
    gap[dep[u]]--;
    if (gap[dep[u]]==0) dep[s]=n+1;
    dep[u]++;
    gap[dep[u]]++;
    return used;
}
int ISAP() {
    M_flow=0;
    while (dep[s]<n) {
        dfs(s,INF);
    }
    return M_flow;
}
signed main() {
    cin>>n>>m>>s>>t;
    while (m--) {
        int u,v,w;
        cin>>u>>v>>w;
        add(u,v,w);
        add(v,u,0);
    }
    cout<<ISAP()<<endl;;
    return 0;
} 

by reveal @ 2023-08-08 20:53:10

ISAP 的 bfs 用于标定初始高度,其满足分层图存在流量。

但是 ISAP 并不要求这点,标定初始高度仅用于减小常数。


by Ayaka_Li @ 2023-08-10 07:07:54

@reveal thx


|