P3376

Aryper · 2021-10-27 16:45:36 · 个人记录

【模板】网络最大流

Edmonds-Karp。

这里从我看的资料里来看，李煜东所著的《算法竞赛进阶指南》中的讲解较为详细易懂。

简单来说，就是在图上不断寻找从 s 到 t 的增广路，直到不存在增广路为止。然后每次找到增广路的 minf，所有 minf 累加起来就是答案。

EK 的时间复杂度是 O(nm^2)。每次 BFS 的复杂度是 O(m)，找增广路的复杂度是 O(nm)。

Dinic 同样是寻找增广路，先构造分层图（保证每一条路径的长度都尽量地短），然后再在这上面做 DFS 增广路。

中间有几个优化，包括当前弧优化（避免重复遍历从 x 出发不可扩展的边），去掉增广完毕的点（流为 0）。

时间复杂度仍然是 O(n^2m)，在求二分图匹配中可达到 O(m\sqrt n)，表现更快。

ISAP 和 Dinic 的复杂度相同，但是效率一般较高。

我们只做一次 BFS，从 t 开始，标记每个点的深度。

然后我们一直搜索做增广路，然后在增广的过程中调整深度，出现深度断层或者起点深度大于 n，就说明找到了最大流。

代码（EK）：

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#define ll long long
using namespace std;

const ll inf=(1ll<<31),N=2e2,M=5e3;

ll n,m,s,t,u,v,w,tot,maxflow;

ll head[N+5],ver[M*2+5],nxt[M*2+5],wt[M*2+5],incf[N+5],pre[N+5];

bool vis[N+5];

bool bfs() {
    memset(vis,0,sizeof(vis));
    queue<ll> q;
    q.push(s);vis[s]=1;
    incf[s]=inf;
    while(!q.empty()) {
        ll h=q.front();q.pop();
        for(ll i=head[h];i;i=nxt[i]) {
            if(!wt[i]||vis[ver[i]]) continue;
            incf[ver[i]]=min(incf[h],wt[i]);
            pre[ver[i]]=i;
            q.push(ver[i]);vis[ver[i]]=1;
            if(ver[i]==t) return 1;
        }
    }
    return 0;
}

void update() {
    ll x=t;
    while(x!=s) {
        ll i=pre[x];
        wt[i]-=incf[t];
        wt[i^1]+=incf[t];
        x=ver[i^1];
    }
    maxflow+=incf[t];
}

void add(ll u,ll v,ll w) {
    ver[++tot]=v;wt[tot]=w;
    nxt[tot]=head[u];head[u]=tot;
    ver[++tot]=u;wt[tot]=0;
    nxt[tot]=head[v];head[v]=tot;
}

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {
        do{buf[++len]=x%10+48;x/=10;}while(x);
    }
    else {
        putchar('-');
        do{buf[++len]=-(x%10)+48;x/=10;}while(x);
    }
    while(len>=0) putchar(buf[len--]);
}

int main() {

    n=read();m=read();s=read();t=read();

    tot=1;
    for(ll i=1;i<=m;i++) {
        u=read();v=read();w=read();
        add(u,v,w);
    }

    while(bfs()) update();

    write(maxflow);

    return 0;
}

代码（Dinic）：

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#define ll long long
using namespace std;

const ll inf=(1ll<<31),N=2e2,M=5e3;

ll n,m,s,t,tot,maxflow,u,v,w;

ll ver[M*2+5],nxt[M*2+5],head[N+5],wt[M*2+5],d[N+5],now[N+5];

queue<ll> q;

bool bfs() {
    memset(d,0,sizeof(d));
    while(!q.empty()) q.pop();
    q.push(s);d[s]=1;now[s]=head[s];
    while(!q.empty()) {
        ll h=q.front();q.pop();
        for(ll i=head[h];i;i=nxt[i]) {
            if(!wt[i]||d[ver[i]]) continue;
            q.push(ver[i]);
            now[ver[i]]=head[ver[i]];
            d[ver[i]]=d[h]+1;
            if(ver[i]==t) return 1;
        }
    }
    return 0;
}

ll dinic(ll x,ll flow) {
    if(x==t) return flow;
    ll rest=flow,k,i;
    for(i=now[x];i&&rest;i=nxt[i]) {
        if(!wt[i]||d[ver[i]]!=d[x]+1) continue;
        k=dinic(ver[i],min(rest,wt[i]));
        if(!k) d[ver[i]]=0;
        wt[i]-=k;wt[i^1]+=k;rest-=k;
        if(rest==0) return flow-rest; 
    }
    now[x]=i;return flow-rest;
}

void add(ll u,ll v,ll w) {
    ver[++tot]=v;wt[tot]=w;
    nxt[tot]=head[u];head[u]=tot;
    ver[++tot]=u;wt[tot]=0;
    nxt[tot]=head[v];head[v]=tot;
}

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {
        do{buf[++len]=x%10+48;x/=10;}while(x);
    }
    else {
        putchar('-');
        do{buf[++len]=-(x%10)+48;x/=10;}while(x);
    }
    while(len>=0) putchar(buf[len--]);
}

int main() {

    n=read();m=read();s=read();t=read();

    tot=1;
    for(ll i=1;i<=m;i++) {
        u=read();v=read();w=read();
        add(u,v,w);
    }

    ll flow=0;
    while(bfs()) {
        while(flow=dinic(s,inf)) maxflow+=flow;
    }

    write(maxflow);

    return 0;
}

代码（ISAP）：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define ll long long
using namespace std;

const ll inf=(1ll<<31),N=2e2,M=5e3;

ll n,m,s,t,tot,u,v,w,maxflow;

ll ver[M*2+5],nxt[M*2+5],head[N+5],edge[M*2+5];
ll dep[N+5],gap[N+5];

void bfs() {
    queue<ll> q;
    q.push(t);gap[dep[t]=1]++;
    while(!q.empty()) {
        ll h=q.front();q.pop();
        for(ll i=head[h];i;i=nxt[i]) {
            if(dep[ver[i]]) continue;
            q.push(ver[i]);
            gap[dep[ver[i]]=dep[h]+1]++;
        }
    }
}

ll dfs(ll p,ll flow) {
    if(p==t) return flow;
    ll rest=flow,k;
    for(ll i=head[p];i;i=nxt[i]) {
        if(!edge[i]||dep[p]!=dep[ver[i]]+1) continue;
        k=dfs(ver[i],min(rest,edge[i]));
        edge[i]-=k;edge[i^1]+=k;rest-=k;
        if(rest==0) return flow-rest;
    }
    if(--gap[dep[p]]==0) dep[s]=n+1;
    gap[++dep[p]]++;
    return flow-rest;
}

void ISAP() {
    bfs();
    while(dep[s]<=n) maxflow+=dfs(s,inf);
}

void add(ll u,ll v,ll w) {
    ver[++tot]=v;edge[tot]=w;nxt[tot]=head[u];head[u]=tot;
    ver[++tot]=u;edge[tot]=0;nxt[tot]=head[v];head[v]=tot;
}

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {
        do{buf[++len]=x%10+48;x/=10;}while(x);
    }
    else {
        putchar('-');
        do{buf[++len]=-(x%10)+48;x/=10;}while(x);
    }
    while(len>=0) putchar(buf[len--]);
}

int main() {

    n=read();m=read();s=read();t=read();

    tot=1;
    for(ll i=1;i<=m;i++) {
        u=read();v=read();w=read();
        add(u,v,w);
    }

    ISAP();

    write(maxflow);

    return 0;
}