[笔记] 网络流从入门到入土

网络是一张有向图，每条边有一个属性：容量，即这条边最多流过的流量。

它具有以下性质：

• 斜对称性质：按照流函数的定义，每条边的反向边其实都有一个负的流量。
• 流量守恒定律：网络中除源点、汇点以外任何节点不存储流，其流入总量等于流出总量。

这里不得不提一下斜对称性，有向图为什么要有反向边？这是为了求解最大流。

网络流模型可以形象的描述为：在不超过容量限制的前提下，流从源点不断产生，流经整个网络，最终全部归于汇点。

最大流

考虑一条残量网络上从S到T的路径，它能增加的流量就是路径上残量的最小值，若最小值大于0，则可以给网络增加流量，称这样的一条路径为一条增广路。

显然，网络达到最大流，当且仅当网络中没有增广路。

寻找最大流，就是一次次地寻找增广路的过程，这个过程可以使用BFS从S到T走一条增广路，这就是EK算法。

根据斜对称性，当一条边流过w单位流量，它的反边就要流过-w单位流量，这就是一个后悔策略。

但是EK算法存在许多不足 ，比如一次只寻找一条增广路，这些可以改进。

Dinic算法：先用BFS将原图分层，再用DFS进行多路增广，达到较优的效果，加上当前弧优化，可以跑1e4~1e5点数的数据。

dinic算法

#include<iostream>
#include<cstring>
#include<cctype>
#include<cstdio>
#include<queue>

using namespace std;

const int MAXN=100005;
const int INF=1<<30;

int n,m,s,t;
int mxflow;

inline int rd(){
    int ret=0,f=1;char c;
    while(c=getchar(),!isdigit(c))f=c=='-'?-1:1;
    while(isdigit(c))ret=ret*10+c-'0',c=getchar();
    return ret*f;
}

struct Edge{
    int next,to,w;
}e[MAXN*10];
int ecnt=1,head[MAXN],cur[MAXN];
inline void add(int x,int y,int w){
    e[++ecnt].next = head[x];
    e[ecnt].to = y;
    e[ecnt].w = w;
    head[x] = ecnt;
}

int dis[MAXN];
bool bfs(){
    queue<int> Q;
    memset(dis,0,sizeof(dis));
    Q.push(s);dis[s]=1;
    while(!Q.empty()){
        int top=Q.front();Q.pop();
        for(int i=head[top];i;i=e[i].next){
            int v=e[i].to;
            if(dis[v]||!e[i].w) continue;
            Q.push(v);dis[v]=dis[top]+1;
        }
    }
    return dis[t];
}

int dfs(int x,int val){
    if(x==t) return val;
    int used=0,tmp;
    for(int i=cur[x];i;i=e[i].next){
        int v=e[i].to;
        if(dis[v]!=dis[x]+1) continue;//
        tmp=dfs(v,min(val-used,e[i].w));
        used+=tmp;
        e[i].w-=tmp;
        e[i^1].w+=tmp;
        if(e[i].w) cur[x]=i;
        if(val==used) return val;
    }
    if(!used) dis[x]=0;
    return used;
}

void dinic(){
    while(bfs()){
        memcpy(cur,head,sizeof(head));
        mxflow+=dfs(s,INF);
    }
}

int main(){
    n=rd();m=rd();
    s=rd();t=rd();
    int x,y,w;
    for(int i=1;i<=m;i++){
        x=rd();y=rd();w=rd();
        add(x,y,w);
        add(y,x,0);
    }
    dinic();
    printf("%d
",mxflow);
    return 0;
}

二分图最大匹配

S向左部点连容量为1的边，右部点向T连容量为1的边，原图边改为从左往右连的容量为1的有向边。

此时最大流=二分图最大匹配。

对二分图如此建图再使用Dinic，总复杂度O(m*sqrt(n))，这就是二分图匹配的Hopcroft-Karp算法

#include<iostream>
#include<cstring>
#include<cctype>
#include<cstdio>
#include<queue>

using namespace std;

const int MAXN=20000;
const int INF=1<<30;

int n,m,s,t;
int mxflow;

inline int rd(){
    int ret=0,f=1;char c;
    while(c=getchar(),!isdigit(c))f=c=='-'?-1:1;
    while(isdigit(c))ret=ret*10+c-'0',c=getchar();
    return ret*f;
}

struct Edge{
    int next,to,w;
}e[1000005];
int ecnt=1,head[MAXN],cur[MAXN];
inline void add(int x,int y,int w){
    e[++ecnt].next = head[x];
    e[ecnt].to = y;
    e[ecnt].w = w;
    head[x] = ecnt;
}

int dis[MAXN];
bool bfs(){
    queue<int> Q;
    memset(dis,0,sizeof(dis));
    Q.push(s);dis[s]=1;
    while(!Q.empty()){
        int top=Q.front();Q.pop();
        for(int i=head[top];i;i=e[i].next){
            int v=e[i].to;
            if(dis[v]||!e[i].w) continue;
            Q.push(v);dis[v]=dis[top]+1;
        }
    }
    return dis[t];
}

int dfs(int x,int val){
    if(x==t) return val;
    int used=0,tmp;
    for(int i=cur[x];i;i=e[i].next){
        int v=e[i].to;
        if(dis[v]!=dis[x]+1) continue;//
        tmp=dfs(v,min(val-used,e[i].w));
        used+=tmp;
        e[i].w-=tmp;
        e[i^1].w+=tmp;
        if(e[i].w) cur[x]=i;
        if(val==used) return val;
    }
    if(!used) dis[x]=0;
    return used;
}

void dinic(){
    while(bfs()){
        memcpy(cur,head,sizeof(head));
        mxflow+=dfs(s,INF);
    }
}

int num;

int main(){
    n=rd();m=rd();num=rd();
    s=n+m+1;t=n+m+2;
    int x,y,w;
    for(int i=1;i<=num;i++){
        x=rd();y=rd();
        if(x>n||y>m) continue;
        add(x,y+n,1);
        add(y+n,x,0);
    }
    for(int i=1;i<=n;i++) add(s,i,1),add(i,s,0);
    for(int i=1;i<=m;i++) add(i+n,t,1),add(t,i+n,0);
    dinic();
    printf("%d
",mxflow);
    return 0;
}

最小割

网络的最大流等于最小割。

最小费用最大流

在每条边上新添加一个属性：花费。即这条边每通过1流量，就要增加一些代价。

最大流大小是确定的，但是流法却可以有很多种，最小费用最大流就是求解在满足最大流的前提下，花费最小的流。

可以将EK算法中寻找增广路的BFS改为SPFA，这样保证既能找到增广路，也满足最小花费。

EK+SPFA算法

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>

using namespace std;

inline int rd(){
    int ret=0,f=1;char c;
    while(c=getchar(),!isdigit(c))f=c=='-'?-1:1;
    while(isdigit(c))ret=ret*10+c-'0',c=getchar();
    return ret*f;
}

const int MAXN=5005;

struct Edge{
    int next,to,w,f;
}e[500005<<1];
int ecnt=1,head[MAXN];
inline void add(int x,int y,int f,int w){
    e[++ecnt].next = head[x];
    e[ecnt].to = y;
    e[ecnt].f = f;
    e[ecnt].w = w;
    head[x] = ecnt;
}

int n,m,s,t;

int dis[MAXN],flow[MAXN],pre[MAXN],inq[MAXN];
queue<int> Q;
bool spfa(){
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0;flow[s]=1<<30;
    Q.push(s);
    while(!Q.empty()){
        int top=Q.front();Q.pop();inq[top]=0;
        for(int i=head[top];i;i=e[i].next){
            int v=e[i].to;
            if(dis[v]<=dis[top]+e[i].w||!e[i].f) continue;
            dis[v]=dis[top]+e[i].w;
            flow[v]=min(flow[top],e[i].f);
            pre[v]=i;
            if(!inq[v]) Q.push(v),inq[v]=1;
        }
    }
    return dis[t]!=0x3f3f3f3f;
}

int ans_flow,ans_cost;
void increase(){
    int cur=t,mx=flow[t];
    while(cur!=s){
        int i=pre[cur];
        e[i].f-=mx;
        e[i^1].f+=mx;
        cur=e[i^1].to;
    }
    ans_flow+=mx;ans_cost+=dis[t]*mx;
}


void EK(){
    while(spfa()) increase();
}


int main(){
    n=rd();m=rd();s=rd();t=rd();
    int x,y,f,w;
    for(int i=1;i<=m;i++){
        x=rd();y=rd();f=rd();w=rd();
        add(x,y,f,w);add(y,x,0,-w);
    }
    EK();
    cout<<ans_flow<<" "<<ans_cost<<endl;
    return 0;
}

zkw费用流

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

inline int rd(){
    int ret=0,f=1;char c;
    while(c=getchar(),!isdigit(c))f=c=='-'?-1:1;
    while(isdigit(c))ret=ret*10+c-'0',c=getchar();
    return ret*f;
}

const int MAXN=5005;
const int M=100005;
const int INF=1<<30;
 
int n,m; 
 
struct Edge{
    int next,to,f,w;
}e[M<<1];
int ecnt=1,head[MAXN],cur[MAXN];
void adds(int x,int y,int f,int w){
    e[++ecnt].next = head[x];
    e[ecnt].to = y;
    e[ecnt].f = f;
    e[ecnt].w = w;
    head[x] = ecnt;
}
void add(int x,int y,int f,int w){
    adds(x,y,f,w);adds(y,x,0,-w);
}
int d[MAXN];
bool vis[MAXN];
int aug(int x,int t,int flow){
    if(x==t) return flow;
    vis[x]=1;int tmp;
    for(int v,&i=cur[x];i;i=e[i].next){
        if(!e[i].f||vis[v=e[i].to]||d[x]!=d[v]+e[i].w)continue;
        tmp=aug(v,t,min(flow,e[i].f));
        if(tmp)return e[i].f-=tmp,e[i^1].f+=tmp,tmp;
    }
    return 0;
}
bool update(){
     int tmp=INF;
     for(int i=1;i<=n;i++){
         if(!vis[i]) continue;
         for(int v,j=head[i];j;j=e[j].next)
             if(e[j].f&&!vis[v=e[j].to])
                 tmp=min(tmp,d[v]+e[j].w-d[i]);
     }
     if(tmp==INF) return true;
     for(int i=1;i<=n;i++)
         if(vis[i]) vis[i]=0,d[i]+=tmp;
     return false;
 }
int mxflow,mncost;
void zkw(int s,int t){
    int tmp;
    while(1){
        memcpy(cur,head,sizeof((head)));
        while(tmp=aug(s,t,INF)){
            mxflow+=tmp;
            mncost+=tmp*d[s];
            memset(vis,0,sizeof(vis));
        }
        if(update())break;
    }
}
     
int main(){    
       int S,T;
    n=rd();m=rd();S=rd();T=rd();
    int x,y,f,w; 
    while (m--){
        x=rd();y=rd();f=rd();w=rd();
        add(x,y,f,w); 
    }
    zkw(S,T);
    printf("%d %d",mxflow,mncost);
    return 0;
  }

无源汇有上下界可行流

为了满足流量守恒，没有源汇的网络显然是一个循环网络。

对于一条弧，可以拆成必要弧和附加弧，必要弧就是这条弧的下界，附加弧是可以在必要弧基础上增广的容量。

必要弧为下界，添加附加弧和附加源汇，看能否跑满出边。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>

using namespace std;

inline int rd(){
    int ret=0,f=1;char c;
    while(c=getchar(),!isdigit(c))f=c=='-'?-1:1;
    while(isdigit(c))ret=ret*10+c-'0',c=getchar();
    return ret*f;
}

const int MAXN=256;
const int M=100005;
const int INF=1<<30;

struct Edge{
    int next,to,f;
}e[M<<1];
int ecnt=1,head[MAXN];
inline void add(int x,int y,int f){
    e[++ecnt].next = head[x];
    e[ecnt].f = f;
    e[ecnt].to =y;
    head[x] = ecnt;
}
int low[M];

int S,T;

int n,m;
int d[MAXN];

int dep[MAXN];
queue<int> Q;
bool bfs(){
    memset(dep,0,sizeof(dep));
    Q.push(S);dep[S]=1;
    while(!Q.empty()){
        int top=Q.front();Q.pop();
        for(int i=head[top];i;i=e[i].next){
            int v=e[i].to;
            if(dep[v]||!e[i].f) continue;
            dep[v]=dep[top]+1;Q.push(v);
        }
    }
    return dep[T];
}
int cur[MAXN];
int dfs(int x,int flow){
    if(x==T) return flow;
    int used=0,tmp;
    for(int i=cur[x];i;i=e[i].next){
        int v=e[i].to;
        if(dep[v]!=dep[x]+1) continue;
        if(!e[i].f) continue;
        tmp=dfs(v,min(e[i].f,flow-used));
        used+=tmp;e[i].f-=tmp;e[i^1].f+=tmp;
        if(used==flow) return flow;
        if(e[i].f) cur[x]=i;
    }
    if(!used) dep[x]=-1;
    return used;
}

int mxflow;
void dinic(){
    while(bfs()){
        memcpy(cur,head,sizeof(head));
        mxflow+=dfs(S,INF);
    }
}
        

int main(){
    n=rd();m=rd();
    int x,y,l,r;
    for(int i=1;i<=m;i++){
        x=rd();y=rd();l=rd();r=rd();
        add(x,y,r-l);add(y,x,0);
        d[x]-=l;d[y]+=l;low[i]=l;
    }
    S=n+1;T=n+2;
    int sum=0;
    for(int i=1;i<=n;i++){
        if(d[i]<0){
            add(i,T,-d[i]);
            add(T,i,0);
        }
        if(d[i]>0){
            add(S,i,d[i]);
            add(i,S,0);
            sum+=d[i];
        }
    }
    dinic();
    if(mxflow<sum) return puts("NO"),0;
    puts("YES");
    for(int i=1;i<=m;i++){
        printf("%d
",low[i]+e[i<<1|1].f);
    }
    return 0;
}

有源汇有上下界可行流

从T向S连一条下界为0，上界为正无穷的边即可转化为无源汇有上下界最大流。

有源汇有上下界最大流

先求出可行流，再从S到T求一次最大流，加上即可。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>

using namespace std;

inline int rd(){
    int ret=0,f=1;char c;
    while(c=getchar(),!isdigit(c))f=c=='-'?-1:1;
    while(isdigit(c))ret=ret*10+c-'0',c=getchar();
    return ret*f;
}

const int MAXN=256;
const int M=100005;
const int INF=1<<30;

struct Edge{
    int next,to,f;
}e[M<<1];
int ecnt=1,head[MAXN];
inline void add(int x,int y,int f){
    e[++ecnt].next = head[x];
    e[ecnt].f = f;
    e[ecnt].to =y;
    head[x] = ecnt;
}
int low[M];

int S,T,SS,TT;

int n,m;
int d[MAXN];

int dep[MAXN];
queue<int> Q;
bool bfs(int x,int y){
    memset(dep,0,sizeof(dep));
    Q.push(x);dep[x]=1;
    while(!Q.empty()){
        int top=Q.front();Q.pop();
        for(int i=head[top];i;i=e[i].next){
            int v=e[i].to;
            if(dep[v]||!e[i].f) continue;
            dep[v]=dep[top]+1;Q.push(v);
        }
    }
    return dep[y];
}
int cur[MAXN];
int dfs(int x,int flow,int arr){
    if(x==arr) return flow;
    int used=0,tmp;
    for(int i=cur[x];i;i=e[i].next){
        int v=e[i].to;
        if(dep[v]!=dep[x]+1) continue;
        if(!e[i].f) continue;
        tmp=dfs(v,min(e[i].f,flow-used),arr);
        used+=tmp;e[i].f-=tmp;e[i^1].f+=tmp;
        if(used==flow) return flow;
        if(e[i].f) cur[x]=i;
    }
    if(!used) dep[x]=-1;
    return used;
}

int mxflow;
void dinic(int x,int y){
    while(bfs(x,y)){
        memcpy(cur,head,sizeof(head));
        mxflow+=dfs(x,INF,y);
    }
}
        

int ans;

int main(){
//    freopen("1.in","r",stdin);
    n=rd();m=rd();S=rd();T=rd();
    int x,y,l,r;
    for(int i=1;i<=m;i++){
        x=rd();y=rd();l=rd();r=rd();
        add(x,y,r-l);add(y,x,0);
        d[x]-=l;d[y]+=l;low[i]=l;
    }
    SS=n+1;TT=n+2;
    
    int sum=0;
    for(int i=1;i<=n;i++){
        if(d[i]<0){
            add(i,TT,-d[i]);
            add(TT,i,0);
        }
        if(d[i]>0){
            add(SS,i,d[i]);
            add(i,SS,0);
            sum+=d[i];
        }
    }
    add(T,S,INF);add(S,T,0);
    int tmp=ecnt;
    dinic(SS,TT);
    ans+=e[tmp].f;
    for(int i=head[SS];i;i=e[i].next){
        if(e[i].f) return puts("please go home to sleep"),0;
    }    
    mxflow=0;
    head[S]=e[head[S]].next;
    head[T]=e[head[T]].next;
    dinic(S,T);
    cout<<ans+mxflow;
    return 0;
}

有源汇有上下界最小流

考虑如何将一些“非必要边”删掉，注意到我们并没有这样的算法，但是根据斜对称性，反边增加流量就是正边减少流量，于是可以在残量网络上求出T到S的最大流，这就是可行流最多可以减去的部分。

先求出可行流，再从T到S求一次最大流，减去即可。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>

using namespace std;

inline int rd(){
    int ret=0,f=1;char c;
    while(c=getchar(),!isdigit(c))f=c=='-'?-1:1;
    while(isdigit(c))ret=ret*10+c-'0',c=getchar();
    return ret*f;
}

const int MAXN=50500;
const int M=200005;
const int INF=1<<30;

struct Edge{
    int next,to,f;
}e[M<<1];
int ecnt=1,head[MAXN];
inline void add(int x,int y,int f){
    e[++ecnt].next = head[x];
    e[ecnt].f = f;
    e[ecnt].to =y;
    head[x] = ecnt;
}
int low[M];

int S,T,SS,TT;

int n,m;
int d[MAXN];

int dep[MAXN];
queue<int> Q;
bool bfs(int x,int y){
    memset(dep,0,sizeof(dep));
    Q.push(x);dep[x]=1;
    while(!Q.empty()){
        int top=Q.front();Q.pop();
        for(int i=head[top];i;i=e[i].next){
            int v=e[i].to;
            if(dep[v]||!e[i].f) continue;
            dep[v]=dep[top]+1;Q.push(v);
        }
    }
    return dep[y];
}
int cur[MAXN];
int dfs(int x,int flow,int arr){
    if(x==arr) return flow;
    int used=0,tmp;
    for(int i=cur[x];i;i=e[i].next){
        int v=e[i].to;
        if(dep[v]!=dep[x]+1) continue;
        if(!e[i].f) continue;
        tmp=dfs(v,min(e[i].f,flow-used),arr);
        used+=tmp;e[i].f-=tmp;e[i^1].f+=tmp;
        if(used==flow) return flow;
        if(e[i].f) cur[x]=i;
    }
    if(!used) dep[x]=-1;
    return used;
}

int mxflow;
void dinic(int x,int y){
    while(bfs(x,y)){
        memcpy(cur,head,sizeof(head));
        mxflow+=dfs(x,INF,y);
    }
}
        

int ans;

int main(){
//    freopen("8.in","r",stdin);
    n=rd();m=rd();S=rd();T=rd();
    int x,y,l,r;
    for(int i=1;i<=m;i++){
        x=rd();y=rd();l=rd();r=rd();
        add(x,y,r-l);add(y,x,0);
        d[x]-=l;d[y]+=l;low[i]=l;
    }
    SS=n+1;TT=n+2;
    
    int sum=0;
    for(int i=1;i<=n;i++){
        if(d[i]<0){
            add(i,TT,-d[i]);
            add(TT,i,0);
        }
        if(d[i]>0){
            add(SS,i,d[i]);
            add(i,SS,0);
            sum+=d[i];
        }
    }
    add(T,S,INF);add(S,T,0);
    int tmp=ecnt;
    dinic(SS,TT);
    ans+=e[tmp].f;
    for(int i=head[SS];i;i=e[i].next){
        if(e[i].f) return puts("please go home to sleep"),0;
    }    
    mxflow=0;
    head[S]=e[head[S]].next;
    head[T]=e[head[T]].next;
    dinic(T,S);
    cout<<ans-mxflow;
    return 0;
}