浅谈最大流:EK和dinic

问:为什么不写预流推进?
答:我不会


正文开始:

最大流是什么

网络流是求出在一个网络内从s点到t点的最大流量的算法。

题目中告诉你s点(起始点),t点(结束点),边以及这条边能流多少流量。

我们最开始并不知道到底该如何走,所以在搜索路径的时候有时走的不是最优解。也可以认为是本来是i点唯一的路径,却被有其他路可以到的j点抢掉了。于是我们为了补偿i点,会建一条反边,i抢掉了多少,就补偿多少反边。

这样最大流的思想就介绍结束了~

EK

EK是直接用BFS搜从s到t的路径。每一次BFS只能找到一条路径。

所有注释都是易错点(都是我错过的地方)

#include<bits/stdc++.h>
using namespace std;
int n,m,s,t;
struct e{
    int nxt,to,sum;
}edge[200005];
int head[10005];
int tot=1;//绝对记得这里tot设为1 
int pre[10005];
int vis[10005];
int minflow[10005];
void add_edge(int u,int v,int w){
    tot++;
    edge[tot].nxt=head[u];
    edge[tot].to=v;
    edge[tot].sum=w;
    head[u]=tot;
}
int BFS(){
    memset(vis,0,sizeof(vis));
    for(int i=0;i<10005;i++){
        minflow[i]=1000000007;
        pre[i]=0;
    }
    queue<int> q;
    q.push(s);
    vis[s]=1;
    int now,nxtt;
    while(!q.empty()){
        now=q.front();
        q.pop();
        if(now==t)return minflow[t];
        for(int i=head[now];i;i=edge[i].nxt){
            nxtt=edge[i].to;
            if(edge[i].sum){//不能写成if(edge[i].sum&&minflow[nxt]>edge[i].sum) 
                if(vis[nxtt])continue;//vis一定要放里面 
                vis[nxtt]=1;
                minflow[nxtt]=min(minflow[now],edge[i].sum);
                pre[nxtt]=i;//这里pre[nxtt]=i而不是now ,不要写错了
                q.push(nxtt);
            }
        }
    }
    return 0;
}
int EK(){
    int maxflow=0,minflow;
    while(minflow=BFS()){
        int nownode=t,nowver;//这个记得放里面 
        while(nownode!=s&&nownode!=0) {
            nowver=pre[nownode];
            edge[nowver].sum-=minflow;
            edge[nowver^1].sum+=minflow;
            nownode=edge[nowver^1].to;
        }
        maxflow+=minflow;
    }
    return maxflow;
}
int main(){
    cin>>n>>m>>s>>t;
    int u,v,w;
    for(int i=0;i<m;i++){
        scanf("%d%d%d",&u,&v,&w);
        add_edge(u,v,w);
        add_edge(v,u,0);
    }
    cout<<EK();
    return 0;
}

dinic

dinic是一次BFS搜索每一个点,对于每一次BFS,用DFS找出路径。

为什么要这样做

我们可以理解为dinic是直接用DFS做,然后BFS是它的优化。这里BFS是为了控制DFS路径的,如果直接用DFS就会炸时间。而当我们先用BFS求出从s点到i点最短路径上i点之前的点,就可以有效控制DFS的路径数。

如果直接DFS炸的很惨。。。如果DFS里面多做了一些步骤也会炸的很惨。。。

#include<bits/stdc++.h>
using namespace std;
int n,m,s,t;
int    pre[10005];
int head[10005];
int maxn=0;
struct e{
    int nxt;
    int to;
    int sum;
}edge[200005];
int tot=1;
int dis[10005];
void add_edge(int u,int v,int w){
    tot++;
    edge[tot].nxt=head[u];
    edge[tot].to=v;
    edge[tot].sum=w;
    head[u]=tot;
}
int vis[10005];
bool BFS(){
    for(int i=0;i<10005;i++){
        vis[i]=0;
        dis[i]=999999999;
        pre[i]=0;
    }
    queue<int> q;
    q.push(s);
    vis[s]=1;
    int now,nxt;
    dis[s]=0;
    while(!q.empty()){
        now=q.front();
        q.pop();
        for(int i=head[now];i;i=edge[i].nxt){
            nxt=edge[i].to;
            if(vis[nxt])continue;
            if(edge[i].sum!=0){
                dis[nxt]=min(dis[nxt],dis[now]+1);
                vis[nxt]=1;
                q.push(nxt);
            }
        }
    }
    if(dis[t]!=999999999){
        return 1;
    }
    return 0;
}
int viss[10005];
int DFS(int now,int minn,int depth){//这个DFS不需要vis数组,因为已经用BFS定型了,每一个节点这可能从一个位置转移过来,也可以说这里的BFS有点像生成树。
    maxn=min(maxn,depth);
    if(now==t){
        return minn;
    }
    int nxt;
    for(int i=head[now];i;i=edge[i].nxt){
        nxt=edge[i].to;
        int tmp;
        
        if(dis[nxt]!=dis[now]+1){
            continue;
        }
        if(edge[i].sum&&viss[nxt]==0){
               
if(tmp=DFS(nxt,min(minn,edge[i].sum),depth+1)){
                pre[nxt]=i;//可以在这里更新剩余流量
                return tmp;
            }
        }
    }
    return 0;
}
int dinic(){
    int minflow,maxflow=0;
    while(BFS()){
        maxn=0;
        while(minflow=DFS(s,999999999,0)){
            int nowver,nownode=t;
            while(nownode!=s){//这里其实可以在DFS的时候更新
                nowver=pre[nownode];
                edge[nowver].sum-=minflow;
                edge[nowver^1].sum+=minflow;
                nownode=edge[nowver^1].to;
            }
            maxflow+=minflow;
        }
    }
    return maxflow;
}
int main(){
    cin>>n>>m>>s>>t;
    int u,v,w;
    for(int i=0;i<m;i++){
        cin>>u>>v>>w;
        add_edge(u,v,w);
        add_edge(v,u,0);
    }
    cout<<dinic();
    return 0;
}

本文链接:http://kaispace.com.cn/index.php/archives/626/

如果未注明出处,复制公开后需将注明本博客链接。
打赏作者