模板 - 最大流 - （新）

update1：通过了【模板】网络最大流的验证。
update2：怎么求出最大流各条边的流量？将原图备份，dinic()后得到残余网络，用原图的流量减去残余网络的剩余流量。

标准模板：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;


namespace Dinic_Maxflow {

    /* 备注：
    1.检查MAXN与MAXM，注意预留反向边和额外边的位置
    2.每次建图的第一次add_edge()前必须先init()
    3.不传入第三参数的dinic(s,t)需保证t是最后的结点
     */

    const int INF=0x3f3f3f3f;

    const int MAXN=20000;
    const int MAXM=200000;
    //注意网络流要预留反向边

    int tol;
    int head[MAXN+5];

    struct Edge {
        int to,next,cap,flow;
    } edge[MAXM+5];


    void init() {
        //.//用来触发编译错误
        tol=2;
        memset(head,-1,sizeof(head));
    }

    //为了方便使用二分图匹配，默认容量为1，默认反向容量为0
    void add_edge(int u,int v,int w=1,int rw=0) {
        edge[tol].to=v;
        edge[tol].cap=w;
        edge[tol].flow=0;
        edge[tol].next=head[u];
        head[u]=tol++;
        edge[tol].to=u;
        edge[tol].cap=rw;
        edge[tol].flow=0;
        edge[tol].next=head[v];
        head[v]=tol++;
    }

    int Q[MAXN+5];
    int dep[MAXN+5],cur[MAXN+5],sta[MAXN+5];

    bool bfs(int s,int t) {
        //front 与 back 的缩写
        int fnt=0,bak=0;
        memset(dep,-1,sizeof(dep[0])*(t+1));
        dep[s]=0;
        Q[bak++]=s;
        while(fnt<bak) {
            int u=Q[fnt++];
            for(int i=head[u]; i!=-1; i=edge[i].next) {
                int v=edge[i].to;
                if(dep[v]==-1&&edge[i].cap>edge[i].flow) {
                    dep[v]=dep[u]+1;
                    if(v==t)
                        return true;
                    Q[bak++]=v;
                }
            }
        }
        return false;
    }

    int dinic(int s,int t) {
        int maxflow=0;
        while(bfs(s,t)) {
            for(int i=0; i<=t; i++)
                cur[i]=head[i];
            int u=s,tail=0;
            while(cur[s]!=-1) {
                if(u==t) {
                    int tp=INF;
                    for(int i=tail-1; i>=0; i--) {
                        tp=min(tp,edge[sta[i]].cap-edge[sta[i]].flow);
                    }
                    maxflow+=tp;
                    for(int i=tail-1; i>=0; i--) {
                        edge[sta[i]].flow+=tp;
                        edge[sta[i]^1].flow-=tp;
                        if(edge[sta[i]].cap-edge[sta[i]].flow==0)
                            tail=i;
                    }
                    u=edge[sta[tail]^1].to;
                } else if(cur[u]!=-1&&edge[cur[u]].cap>edge[cur[u]].flow
                          &&dep[u]+1==dep[edge[cur[u]].to]) {
                    sta[tail++]=cur[u];
                    u=edge[cur[u]].to;
                } else {
                    while(u!=s&&cur[u]==-1) {
                        u=edge[sta[--tail]^1].to;
                    }
                    cur[u]=edge[cur[u]].next;
                }
            }
        }
        return maxflow;
    }

    /* 备注：
    1.检查MAXN与MAXM，注意预留反向边和额外边的位置
    2.每次建图的第一次addedge()前必须先init()
    3.不传入第三参数的dinic(s,t)需保证t是最后的结点
     */

}


using namespace Dinic_Maxflow;


int main() {
    int n,m,s1,t1;
    scanf("%d%d%d%d",&n,&m,&s1,&t1);
    init();

    int s=0,t=n+1;
    add_edge(s,s1,INF);
    add_edge(t1,t,INF);

    for(int i=1; i<=m; i++) {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        add_edge(u,v,w);
    }

    printf("%d\n",dinic(s,t));
}

缩写模板：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;


namespace Dinic_Maxflow {

    /* 备注：
    1.检查MAXN与MAXM，注意预留反向边和额外边的位置
    2.每次建图的第一次add_edge()前必须先init()
    3.不传入第三参数的dinic(s,t)需保证t是最后的结点
     */

    const int INF=0x3f3f3f3f;

    const int MAXN=20000;
    const int MAXM=200000;
    //注意网络流要预留反向边

    //edge_top,head 的 缩写
    int et;
    int hd[MAXN+5];

    struct Edge {
        //to,next,cap,flow 的 缩写
        int t,n,c,f;
    } e[MAXM+5];


    void init() {
        //.//用来触发编译错误
        et=2;
        memset(hd,-1,sizeof(hd));
    }

    //为了方便使用二分图匹配，默认容量为1，默认反向容量为0
    void add_edge(int u,int v,int c=1,int rc=0) {
        e[et].t=v;
        e[et].c=c;
        e[et].f=0;
        e[et].n=hd[u];
        hd[u]=et++;
        e[et].t=u;
        e[et].c=rc;
        e[et].f=0;
        e[et].n=hd[v];
        hd[v]=et++;
    }

    int Q[MAXN+5];
    int dep[MAXN+5],cur[MAXN+5],sta[MAXN+5];
    bool bfs(int s,int t) {
        //front 与 back 的缩写
        int fnt=0,bak=0;
        memset(dep,-1,sizeof(dep[0])*(t+1));
        dep[s]=0;
        Q[bak++]=s;
        while(fnt<bak) {
            int u=Q[fnt++];
            for(int i=hd[u]; i!=-1; i=e[i].n) {
                int v=e[i].t;
                if(e[i].c>e[i].f&&dep[v]==-1) {
                    dep[v]=dep[u]+1;
                    if(v==t)
                        return true;
                    Q[bak++]=v;
                }
            }
        }
        return false;
    }

    int dinic(int s,int t) {
        int maxflow=0;
        while(bfs(s,t)) {
            for(int i=0; i<=t; i++)
                cur[i]=hd[i];
            //tail 的 缩写
            int u=s,tl=0;
            while(cur[s]!=-1) {
                if(u==t) {
                    int tp=INF;
                    for(int i=tl-1; i>=0; i--) {
                        tp=min(tp,e[sta[i]].c-e[sta[i]].f);
                    }
                    maxflow+=tp;
                    for(int i=tl-1; i>=0; i--) {
                        e[sta[i]].f+=tp;
                        e[sta[i]^1].f-=tp;
                        if(e[sta[i]].c-e[sta[i]].f==0)
                            tl=i;
                    }
                    u=e[sta[tl]^1].t;
                } else if(cur[u]!=-1&&e[cur[u]].c>e[cur[u]].f
                          &&dep[u]+1==dep[e[cur[u]].t]) {
                    sta[tl++]=cur[u];
                    u=e[cur[u]].t;
                } else {
                    while(u!=s&&cur[u]==-1) {
                        u=e[sta[--tl]^1].t;
                    }
                    cur[u]=e[cur[u]].n;
                }
            }
        }
        return maxflow;
    }

    /* 备注：
    1.检查MAXN与MAXM，注意预留反向边和额外边的位置
    2.每次建图的第一次addedge()前必须先init()
    3.不传入第三参数的dinic(s,t)需保证t是最后的结点
     */

}


using namespace Dinic_Maxflow;


int main() {
    int n,m,s1,t1;
    scanf("%d%d%d%d",&n,&m,&s1,&t1);
    init();

    int s=0,t=n+1;
    add_edge(s,s1,INF);
    add_edge(t1,t,INF);

    for(int i=1; i<=m; i++) {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        add_edge(u,v,w);
    }

    printf("%d\n",dinic(s,t));
}

扫码关注我们

微信号：SRE实战

拒绝背锅 运筹帷幄

×

选择打赏方式：

微信 QQ钱包 支付宝

打赏

打赏

打赏

多少都是心意！谢谢大家！！！