二分图/网络流/最小割/最大流/最小费用最大流等等模板

二分图匹配：

1.Hungary O(n * m) n为二分图左侧点数 m为二分图右侧点数

#include<bits/stdc++.h>
using namespace std;
const int N=1e7;
struct node{
    int from,to,nxt;
}e[N];
int head[N],cnt;
int n;
int v[N],ans,A,B,d[N];
void add(int from,int to){
    e[++cnt].nxt=head[from];
    e[cnt].from=from;
    e[cnt].to=to;
    head[from]=cnt;
    return;
}
bool ok(int from){
    for(int i=head[from];i;i=e[i].nxt){
        int to=e[i].to;
        if(!v[to]){
            v[to]=1;
            if(d[to]==-1||ok(d[to])){
                d[to]=from;
                return 1;
            }
        }
    }
    return 0;
}
int main(){
    scanf("%d%d%d",&A,&B,&n);
    for(int i=1;i<=n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        if(x>A||y>B)continue;
        add(x,y);
    }
    memset(d,-1,sizeof d);
    for(int i=1;i<=A;i++){
        for(int j=1;j<=B;j++)v[j]=0;
        if(ok(i))ans++;
    }
    printf("%d",ans);
}

Hungary

2.Dinic O(n * √m) n,m含义同上

#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=3000010;
int s,t,n,m,x,y,z,maxflow,deep[N],A,B;
struct Edge{
    int next,to,w;
}e[N];
int cnt=-1,head[N],cur[N];
queue<int >q;
void add(int from,int to,int w){
    e[++cnt].next=head[from];
    e[cnt].to=to;
    e[cnt].w=w;
    head[from]=cnt;
}
bool bfs(int s,int t){
    for(int i=0;i<=n+1;i++)deep[i]=inf; 
    for(int i=0;i<=n+1;i++)cur[i]=head[i]; 
    while(!q.empty())q.pop();
    deep[s]=0;
    q.push(s);
    while(!q.empty()){
        int from=q.front();
        q.pop();
        for(int i=head[from];i!=-1;i=e[i].next){
            if(deep[e[i].to]==inf&&e[i].w){
                deep[e[i].to]=deep[from]+1;
                q.push(e[i].to);
            }
        }
    }
    if(deep[t]<inf)return 1;
    else return 0;
}
int dfs(int from,int t,int limit){
    if(!limit||from==t)return limit;
    int flow=0,f;
    for(int i=cur[from];i!=-1;i=e[i].next){
        int to=e[i].to;
        cur[from]=i;
        if(deep[to]==deep[from]+1&&(f=dfs(to,t,min(limit,e[i].w)))){
            flow+=f;
            limit-=f;
            e[i].w-=f;
            e[i^1].w+=f;
            if(!limit)break;
        }
    }
    return flow;
}
void dinic(int s,int t){
    while(bfs(s,t)){
        maxflow+=dfs(s,t,inf);
    }
}
int main(){
    memset(head,-1,sizeof head);
    scanf("%d%d%d",&A,&B,&m);
    s=0;
    t=A+B+1;
    n=A+B+1;
    for(int i=1;i<=A;i++){
        add(s,i,1);
        add(i,s,0);
    }
    for(int i=A+1;i<=A+B;i++){
        add(i,t,1);
        add(t,i,0);
    }
    for(int i=1;i<=m;i++){
        scanf("%d%d",&x,&y);
        if(x>A||y>B)continue;
        y+=A;
        add(x,y,1);
        add(y,x,0);
    }
    dinic(s,t);
    printf("%d",maxflow);
    return 0;
}

Dinic

二分图小知识: 最大边覆盖=最大独立子集=总点数-最小点覆盖=总点数-最大匹配 (二分图中)

最大流/最小割：

(指定源点汇点时)

1.Dinic O(n²* m) n为点数 m为边数代码里加入了当前弧优化

#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=3020000;
int s,t,n,m,x,y,z,maxflow,deep[N];
struct Edge{
    int next,to,w;
}e[N];
int cnt=-1,head[N],cur[N];
queue<int >q;
void add(int from,int to,int w){
    e[++cnt].next=head[from];
    e[cnt].to=to;
    e[cnt].w=w;
    head[from]=cnt;
}
bool bfs(int s,int t){
    for(int i=0;i<=n+1;i++)deep[i]=inf;
    for(int i=1;i<=n;i++)cur[i]=head[i];
    deep[s]=0;
    q.push(s);
    while(!q.empty()){
        int from=q.front();
        q.pop();
        for(int i=head[from];i!=-1;i=e[i].next){
            int to=e[i].to;
            if(deep[to]==inf&&e[i].w){
                deep[to]=deep[from]+1;
                q.push(to);
            }
        }
    }
    if(deep[t]<inf)return 1;
    else return 0;
}
int dfs(int from,int t,int limit){
    if(!limit||from==t)return limit;
    int flow=0,f;
    for(int i=cur[from];i!=-1;i=e[i].next){
        cur[from]=i;
        int to=e[i].to;
        if(deep[to]==deep[from]+1&&(f=dfs(to,t,min(limit,e[i].w)))){
            flow+=f;
            limit-=f;
            e[i].w-=f;
            e[i^1].w+=f;
            if(!limit)break;
        }
    }
    return flow;
}
void dinic(int s,int t){
    while(bfs(s,t)){
        maxflow+=dfs(s,t,inf);
    }
}
int main(){
    memset(head,-1,sizeof head);
    scanf("%d%d%d%d",&n,&m,&s,&t);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
        add(y,x,0);
    }
    dinic(s,t);
    printf("%d",maxflow);
    return 0;
}

Dinic

另外Dinic还有两个不常用的优化：

①：O(n * m *logC ) C为最大边的容量具体做法是将边的容量按二进制排序位数相同的分为一组以位数从低到高枚举每一组添加到残余网络中并做一遍dinic贡献答案。

②：在①的基础上O(玄学) 具体做法是跑①时先不加如反向边跑完①后再将反向边加入残余网络并做一遍dinic贡献答案

至于原理嘛...貌似①在算导上有思考题

2.EK O(n * m²) n,m含义同上 (可能全网只有我一个人这么闲写的链式向前星)

#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=3020000;
int s,t,n,m,x,y,z,maxflow,limit[N],bac[N],pre[N];
struct Edge{
    int next,to,w;
}e[N];
int cnt=-1,head[N];
queue<int >q;
void add(int from,int to,int w){
    e[++cnt].next=head[from];
    e[cnt].to=to;
    e[cnt].w=w;
    head[from]=cnt;
}
int bfs(int s,int t){
    for(int i=1;i<=n;i++)pre[i]=-1;
    pre[s]=0;
    q.push(s);
    limit[s]=inf;
    while(!q.empty()){
        int from=q.front();
        q.pop();
        if(from==t)break;
        for(int i=head[from];i!=-1;i=e[i].next){
            int to=e[i].to;
            if(pre[to]==-1&&e[i].w>0){
                pre[to]=from;
                bac[to]=i;
                limit[to]=min(limit[from],e[i].w);
                q.push(to);
            }
        }
    }
    if(pre[t]!=-1)return limit[t];
    else return 0;
}
void EK(int s,int t){
    int flow=0; 
    while(flow=bfs(s,t)){
        int k=t;
        while(k!=s){
            e[bac[k]].w-=flow;
            e[bac[k]^1].w+=flow;
            k=pre[k];
        }
        maxflow+=flow;
    }
}
int main(){
    memset(head,-1,sizeof head);
    scanf("%d%d%d%d",&n,&m,&s,&t);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
        add(y,x,0);
    }
    EK(s,t);
    printf("%d",maxflow);
    return 0;
}

3.ISAP 理论时间复杂度与Dinic相同但二分图时ISAP更有优势
(另外由于ISAP预处理出来了大致的最大流路径故当网络流中途带修时ISAP需要重新做bfs 因此优先考虑其他网络流算法)

#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=3020000;
int s,t,n,m,x,y,z,maxflow,deep[N],lay[N];
struct Edge{
    int next,to,w;
}e[N];
int cnt=-1,head[N],cur[N];
queue<int >q;
void add(int from,int to,int w){
    e[++cnt].next=head[from];
    e[cnt].to=to;
    e[cnt].w=w;
    head[from]=cnt;
}
void bfs(int s,int t){
    for(int i=0;i<=n+1;i++){
        deep[i]=inf;
        lay[i]=0;
    } 
    deep[t]=0;
    lay[0]=1;
    q.push(t);
    while(!q.empty()){
        int from=q.front();
        q.pop();
        for(int i=head[from];i!=-1;i=e[i].next){
            int to=e[i].to;
            if(deep[to]==inf){
                deep[to]=deep[from]+1;
                lay[deep[to]]++;
                q.push(to);
            }
        }
    }
    return;
}
int dfs(int from,int t,int limit){
    if(from==t){
        maxflow+=limit;
        return limit;
    }
    int flow=0;
    for(int i=cur[from];i!=-1;i=e[i].next){
        int to=e[i].to;
        cur[from]=i;
        if(deep[to]+1==deep[from]&&e[i].w){
            int f=dfs(to,t,min(e[i].w,limit));
            flow+=f;
            limit-=f;
            e[i].w-=f;
            e[i^1].w+=f;
            if(!limit)return flow;
        }
    }
    lay[deep[from]]--;
    if(lay[deep[from]]==0)deep[s]=n+1;
    deep[from]++;
    lay[deep[from]]++;
    return flow;
}
void ISAP(int s,int t){
    bfs(s,t);
    while(deep[s]<n){
        for(int i=1;i<=n;i++)cur[i]=head[i];
        dfs(s,t,inf);
    }
}
int main(){
    memset(head,-1,sizeof head);
    scanf("%d%d%d%d",&n,&m,&s,&t);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
        add(y,x,0);
    }
    ISAP(s,t);
    printf("%d",maxflow);
    return 0;
}

ISAP

4.HLPP(以后补上)

(没指定源点汇点,只问割边使原图变成两个强连通分量的最小割时)

1.Stoer-Wagner O(n³) n为点数如果加入prim堆优化可以优化到O(n²logn) (蒟蒻不会prim堆优化)

#include<bits/stdc++.h>
using namespace std;
const int MAX=0x3f3f3f3f;
int W[100010],merged[100010],v[100010],mapp[1001][1001];
int S,T,n,m;
int step(){
    int ans=MAX,next=T,maxW;
    for(int i=1;i<=n;i++){
        W[i]=0,v[i]=0;
    }
    for(int i=1;i<=n;i++){
        maxW=-1;
        for(int j=1;j<=n;j++){
            if(!merged[j]&&!v[j]&&maxW<W[j]){
                maxW=W[j];
                next=j;
            }
        }
        if(next==T)break;
        v[next]=1;
        S=T,T=next,ans=maxW;
        for(int j=1;j<=n;j++){
            if(!merged[j]&&!v[j])W[j]+=mapp[T][j];
        }
    }
    return ans;
}
int sto(){
    int ans=MAX;
    for(int i=1;i<n;i++){
        ans=min(ans,step());
        if(!ans)return 0;
        merged[T]=1;
        for(int j=1;j<=n;j++){
            mapp[S][j]+=mapp[T][j];
            mapp[j][S]+=mapp[j][T];
        }
    }
    return ans;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        mapp[x][y]=mapp[y][x]=z;
    }
    printf("%d",sto());
}

Stoer-Wagner

最小费用最大流:

1.EK 时间复杂度O(n * m²) 代码实现将bfs换成了 spfa/其他最短路算法而已

spfa版本:

#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=120000;
int s,t,n,m,x,y,z,d,maxflow,mincost,limit[N],bac[N],pre[N],dis[N],v[N];
struct Edge{
    int next,to,w,dis;
}e[N];
int cnt=-1,head[N];
queue<int >q;
void add(int from,int to,int w,int dis){
    e[++cnt].next=head[from];
    e[cnt].to=to;
    e[cnt].w=w;
    e[cnt].dis=dis;
    head[from]=cnt;
}
int spfa(int s,int t){
    for(int i=1;i<=n;i++){
        dis[i]=inf;
        limit[i]=inf;
        v[i]=0;
    }
    pre[t]=-1;
    q.push(s);
    dis[s]=0;
    v[s]=1;
    while(!q.empty()){
        int from=q.front();
        q.pop();
        v[from]=0; 
        for(int i=head[from];i!=-1;i=e[i].next){
            int to=e[i].to;
            if(dis[to]>dis[from]+e[i].dis&&e[i].w>0){
                dis[to]=dis[from]+e[i].dis;
                pre[to]=from;
                bac[to]=i;
                limit[to]=min(limit[from],e[i].w);
                if(!v[to]){
                    v[to]=1;
                    q.push(to);
                }
            }
        }
    }
    if(pre[t]!=-1)return limit[t];
    else return 0;
}
void MCMF(int s,int t){
    int flow=0; 
    while(flow=spfa(s,t)){
        int k=t;
        while(k!=s){
            e[bac[k]].w-=flow;
            e[bac[k]^1].w+=flow;
            k=pre[k];
        }
        mincost+=flow*dis[t];
        maxflow+=flow;
    }
}
int main(){
    memset(head,-1,sizeof head);
    scanf("%d%d%d%d",&n,&m,&s,&t);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d%d",&x,&y,&z,&d);
        add(x,y,z,d);
        add(y,x,0,-d);
    }
    MCMF(s,t);
    printf("%d %d",maxflow,mincost);
    return 0;
}

djk版本:(以后补上)

上下界网络流:

1.无源汇上下界可行流:

#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=3020000;
int s,t,n,m,x,y,z,maxflow,deep[N],lay[N],low[N],high[N],out[N],sum;
struct Edge{
    int next,to,w;
}e[N];
int cnt=-1,head[N],cur[N];
queue<int >q;
void add(int from,int to,int w){
    e[++cnt].next=head[from];
    e[cnt].to=to;
    e[cnt].w=w;
    head[from]=cnt;
}
void bfs(int s,int t){
    for(int i=0;i<=n+1;i++){
        deep[i]=inf;
        lay[i]=0;
    } 
    deep[t]=0;
    lay[0]=1;
    q.push(t);
    while(!q.empty()){
        int from=q.front();
        q.pop();
        for(int i=head[from];i!=-1;i=e[i].next){
            int to=e[i].to;
            if(deep[to]==inf){
                deep[to]=deep[from]+1;
                lay[deep[to]]++;
                q.push(to);
            }
        }
    }
    return;
}
int dfs(int from,int t,int limit){
    if(from==t){
        maxflow+=limit;
        return limit;
    }
    int flow=0;
    for(int i=cur[from];i!=-1;i=e[i].next){
        int to=e[i].to;
        cur[from]=i;
        if(deep[to]+1==deep[from]&&e[i].w){
            int f=dfs(to,t,min(e[i].w,limit));
            flow+=f;
            limit-=f;
            e[i].w-=f;
            e[i^1].w+=f;
            if(!limit)return flow;
        }
    }
    lay[deep[from]]--;
    if(lay[deep[from]]==0)deep[s]=n+1;
    deep[from]++;
    lay[deep[from]]++;
    return flow;
}
void ISAP(int s,int t){
    bfs(s,t);
    while(deep[s]<n){
        for(int i=1;i<=n;i++)cur[i]=head[i];
        dfs(s,t,inf);
    }
}
int main(){
    memset(head,-1,sizeof head);
    scanf("%d%d",&n,&m);
    s=n+1,t=n+2;
    for(int i=0;i<m;i++){//×¢Òâ m´Ó0¿ªÊ¼ 
        scanf("%d%d%d%d",&x,&y,&low[i],&high[i]);
        add(x,y,high[i]-low[i]);
        add(y,x,0);
        out[x]-=low[i];
        out[y]+=low[i];
    }
    for(int i=1;i<=n;i++){
        if(out[i]>0){
            sum+=out[i];
            add(s,i,out[i]);
            add(i,s,0);
        }else if(out[i]<0){
            add(i,t,-out[i]);
            add(t,i,0);
        }
    }
    n=n+2;
    ISAP(s,t);
    if(maxflow!=sum){
        printf("NOn");
    }else{
        printf("YESn");
        for(int i=0;i<m;i++){
            printf("%dn",e[i*2|1].w+low[i]);
        }
    }
    return 0;
}

ISAP

2.有源汇上下界最大/最小/可行流:

#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=9000300;
int s,t,S,T,n,m,x,y,z,maxflow,deep[N],lay[N],low[N],high[N],out[N],sum;
struct Edge{
    int next,to,w;
}e[N],E[N];
int cnt=-1,num,tot,head[N],cur[N],Head[N];
int ans;
queue<int >q;
void add(int from,int to,int w){
    e[++cnt].next=head[from];
    e[cnt].to=to;
    e[cnt].w=w;
    head[from]=cnt;
}
bool bfs(int s,int t){
    for(int i=0;i<=n+1;i++)deep[i]=inf;
    for(int i=1;i<=n;i++)cur[i]=head[i];
    deep[s]=0;
    q.push(s);
    while(!q.empty()){
        int from=q.front();
        q.pop();
        for(int i=head[from];i!=-1;i=e[i].next){
            int to=e[i].to;
            if(deep[to]==inf&&e[i].w){
                deep[to]=deep[from]+1;
                q.push(to);
            }
        }
    }
    if(deep[t]<inf)return 1;
    else return 0;
}
int dfs(int from,int t,int limit){
    if(!limit||from==t)return limit;
    int flow=0,f;
    for(int i=cur[from];i!=-1;i=e[i].next){
        cur[from]=i;
        int to=e[i].to;
        if(deep[to]==deep[from]+1&&(f=dfs(to,t,min(limit,e[i].w)))){
            flow+=f;
            limit-=f;
            e[i].w-=f;
            e[i^1].w+=f;
            if(!limit)break;
        }
    }
    return flow;
}
void dinic(int s,int t){
    while(bfs(s,t)){
        maxflow+=dfs(s,t,inf);
    }
}
int main(){
    memset(head,-1,sizeof head);
    scanf("%d%d%d%d",&n,&m,&S,&T);
    s=n+1,t=n+2;
    for(int i=0;i<m;i++){
        scanf("%d%d%d%d",&x,&y,&low[i],&high[i]);
        add(x,y,high[i]-low[i]);
        add(y,x,0);
        out[x]-=low[i];
        out[y]+=low[i];
    }
    for(int i=1;i<=n;i++){
        if(out[i]>0){
            sum+=out[i];
            add(s,i,out[i]);
            add(i,s,0);
        }else if(out[i]<0){
            add(i,t,-out[i]);
            add(t,i,0);
        }
    }
    add(T,S,inf);
    add(S,T,0);
    n=n+2;
    dinic(s,t);
    s=T,t=S;
    if(maxflow!=sum){//ÅÐ¶ÏÊÇ·ñÎªÓÐÔ´»ãÉÏÏÂ½ç¿ÉÐÐÁ÷ 
        printf("please go home to sleepn");
    }else{
        ans=e[cnt].w;
        e[cnt].w=0;
        e[cnt^1].w=0;
        s=S,t=T;
        //ÒÔÏÂÎªÇó³öÓÐÔ´»ãÉÏÏÂ½ç×î´óÁ÷     
        maxflow=0;
        dinic(s,t);
        ans+=maxflow;
        printf("%dn",ans); 
        //ÒÔÏÂÎªÇó³öÓÐÔ´»ãÉÏÏÂ½ç×îÐ¡Á÷ 
        maxflow=0;
        dinic(T,S);
        ans-=maxflow;
        printf("%dn",ans);
    }
    return 0;
}

Dinic

3.上下界费用流：待补

原文链接: https://www.cnblogs.com/passione-123456/p/12234799.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/325208

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

二分图/网络流/最小割/最大流/最小费用最大流等等 模板

相关推荐

二分图/网络流/最小割/最大流/最小费用最大流等等模板