碎碎念

为什么$CSP$不考网络流嘤嘤嘤。

好像很多是当时在其他$Dalao$上复制的.....$QAQ$

网络流

什么是网络流

在一个有向图上选择一个源点,一个汇点

每一条边上都有一个流量上限(以下称为容量)。

同时,除源点和汇点外,所有点的入流和出流都相等

而源点只有流出的流,汇点只有汇入的流。

这样的图叫做网络流

定义

源点:只有流出去的点
汇点:只有流进来的点
流量:一条边上流过的流量
容量:一条边上可供流过的最大流量
残量:一条边上的容量-流量

最大流

最大流算法就是指的一个流量的方案使得网络中流量最大

增广路思想

网络流的所有算法都是基于一种增广路的思想,其基本步骤如下:

①找到一条从源点到汇点的路径,使得路径上任意一条边的残量>0

(注意是大于而不是大于等于,这意味着这条边还可以分配流量),这条路径便称为增广路

②找到这条路径上最小的$F[u][v]$(我们设$F[u][v]$表示$u->v$这条边上的残量即剩余流量),下面记为$flow$

③将这条路径上的每一条有向边$u->v$的残量减去$flow$,同时对于其反向边$v->u$的残量加上$flow$

④重复上述过程,直到找不出增广路,此时我们就找到了最大流。

为什么要连反向边?

我们知道,当我们在寻找增广路的时候,在前面找出的不一定是最优解。

如果我们在减去残量网络中正向边的同时将相对应的反向边加上对应的值,我们就相当于可以反悔从这条边流过。

$ps$:将建双向边的操作压在一个$add$中可以让主函数看着短点...

EK算法

直接从$S$到$T$广搜即可,通过权值大于$0$的边,直到找到$T$为止。

找到该路径上边权最小的边,记为$Flow$,最大流加上$Flow$。该路径上的每一条边的边权减去$Flow$,

然后把该路径上的每一条边的反向边的边权加上$Flow$,直到找不到一条增广路为止。

bool bfs(){
    while(!q.empty()) q.pop(); 
    memset(vis,0,sizeof(vis));
    memset(pre_node,-1,sizeof(pre_node));
    vis[s]=1; q.push(s);
    while(!q.empty()){
        int x=q.front(); q.pop();
        for(int i=first[x];i;i=line[i].nextt){
            int y=line[i].to;
            int w=line[i].p;
            if(!vis[y]&&w){
                vis[y]=1;
                pre_node[y]=x;
                pre_edge[y]=i;
                if(y==t) return 1;
                q.push(y);
            }
        }
    }
    return 0;
}
int EK(){
    int ans=0;
    while(bfs()){
        int flow=inf;
        for(int i=t;i!=s;i=pre_node[i]){
            flow=min(flow,line[pre_edge[i]].p);
        }
        for(int i=t;i!=s;i=pre_node[i]){
            line[pre_edge[i]].p-=flow;
            line[pre_edge[i]^1].p+=flow;
        }
        ans+=flow;
    }
    return ans;
}

Dinic

这个算法是基于增广路定理($Augmenting\ Path\ Theorem$): 网络达到最大流当且仅当残留网络中没有增广路。

变量定义
int n,m,s,t;//点数,边数,源点,汇点 
struct data{
    int to;
    int p;//每一条边的残量
    int nextt;
}line[2*maxm];//存反向要开两倍! 
int first[maxn];
int now[maxn];//记录当前点x循环到了哪一条边 
int tail=1;//tail从2开始 2^1=3 3^1=2 可以轻松地找到反向边
void add(int x,int y,int w){
    tail++;
    line[tail].to=y;
    line[tail].p=w;
    line[tail].nextt=first[x];
    first[x]=tail;
}
Dinic求主过程
int Dinic(){
    int maxf=0;//记录最大流量
    while(bfs()){
        memcpy(now,first,sizeof(now));
        //每一次建立完分层图后都要把now置为每一个点的第一条边
        while(int di=dfs(s,inf)){
            maxf+=di;
        }
    }
    return maxf;
}
bfs分层图过程
bool bfs(){
    while(!q.empty()) q.pop();
    memset(dep,0,sizeof(dep));//每次分层时要清零
    dep[s]=1; q.push(s);
    while(!q.empty()){
        int x=q.front(); q.pop();
        for(int i=first[x];i;i=line[i].nextt){
            int y=line[i].to;
            int w=line[i].p;
            if(w&&!dep[y]){
            //若该残量不为0,且y还未分配深度,则给其分配深度并放入队列。 
                dep[y]=dep[x]+1;
                q.push(y);
            }
        }
    }
    //当汇点的深度不存在时,说明不存在分层图,同时也说明不存在增广路
    return dep[t];
}
dfs寻找增广路过程
int dfs(int x,int flow){//x是当前节点,flow是当前流量
    if(x==t) return flow;
    for(int &i=now[x];i;i=line[i].nextt){
        int y=line[i].to;
        int w=line[i].p;
        if(dep[y]==dep[x]+1&&w){
            //注意这里要满足分层图和残量不为0两个条件
            int di=dfs(y,min(flow,w));//向下增广
            if(!di) dep[y]=0;//剪枝,去掉增广完的点 
            if(di>0){//若增广成功
                line[i].p-=di;//正向边减
                line[i^1].p+=di;//反向边加
                return di;//向上传递
            }
        }
    }
    return 0;//否则说明没有增广路,返回0
}
注意

• 多路增广 每次不是寻找一条增广路,而是在$DFS$中,只要可以就递归增广下去,实际上形成了一张增广网。

• 当前弧优化 对于每一个点,都记录上一次检查到哪一条边。

​ 因为我们每次增广一定是彻底增广(每访问一条边都会把它榨干)。

​ 下 一次就不必再检查它,而直接看第一个未被检查的边。

• 去掉无用的点 对于一个点,如果在残留网络中从它出发到汇点不在有增广路。

​ 则下一次就不必再经过它,可以将其深度删除。

如何求出最大流中每条边的流量

将原图备份,原图上的边的容量减去做完最大流的残余网络上的边的剩余容量,就是边的流量。

最小割

给定一个网格,源点为$S$,汇点为$T$。

若一个边集被删去后,源点$S$ 和汇点$T$不再连通,则称改边集为网络的

边的容量之和最小的割称为网络的最小割

最大流最小割定理

最大流等于最小割(记就完了)。

证明

当达到最大流时,根据增广路定理。

残留网络中$s$到$t$已经没有通路了,否则还能继续增广。

我们把s能到的的点集设为$S$,不能到的点集为$T$。

构造出一个割集$C[S,T]$,$S$到$T$的边必然满流 否则就能继续增广。

这些满流边的流量和就是当前的流即最大流。

把这些满流边作为割,就构造出了一个和最大流相等的割。

费用流

在最大流的基础上每一条边增加一个参数:每个单位流量的费用。

求解在最大流的情况下最小的费用。

EK

EK算法,即$SPFA$+增广路

在图上 以费用为边权 跑$SPFA$:

最小的总费用就是累计$(当前路径所流总量)\times(s到t的最短路径)$

bool SPFA(){
    while(!q.empty()) q.pop(); 
    memset(dist,0x3f,sizeof(dist));
    memset(inqueue,0,sizeof(inqueue));
    dist[s]=0;
    q.push(s); inqueue[s]=1;
    while(!q.empty()){
        int x=q.front();
        q.pop(); inqueue[x]=0;
        for(int i=first[x];i;i=line[i].nextt){
            int y=line[i].to;
            int w=line[i].p;
            int c=line[i].val;
            if(w&&dist[y]>dist[x]+c){
                dist[y]=dist[x]+c;
                pre_node[y]=x;
                pre_edge[y]=i;
                if(inqueue[y]==0){
                    inqueue[y]=1;
                    q.push(y);    
                }
            }
        }
    }
    return dist[t]!=inf;
}
void EK(){
    int ansf=0,ansc=0;
    while(SPFA()){
        int flow=inf;
        for(int i=t;i!=s;i=pre_node[i]){
            flow=min(flow,line[pre_edge[i]].p);
        }
        for(int i=t;i!=s;i=pre_node[i]){
            line[pre_edge[i]].p-=flow;
            line[pre_edge[i]^1].p+=flow;
        }
        ansf+=flow;
        ansc+=flow*dist[t];
    }
    cout<<ansf<<" "<<ansc<<endl;
}
注意

连接双向边时,反向边的单位费用为正向边的相反数$!!!$

网络流模型总结

它咕了。