时间戳

首页 > 技术文章 > 网络流总结

网络流总结

newera 2018-02-05 22:18 原文

如此繁复多样的一类问题，就先从模板开始吧

1、最大流算法

模板题：https://www.luogu.org/problemnew/show/P3376

以下所有模板皆以上述问题为准

 

（1）FF算法（Ford-Fulkerson）

这便是最基础的一种增广路算法。

而所有增广路算法都使用了一种重要的技巧：对所有edge.cap>0的边构造反向边rev(e)。

而在我个人看来，构造反向边的精妙之处就在于它使得两个看上去不相干的较难处理的操作化为了一个符合dfs基本法的操作，即所谓的“退流”。

 

e.cap减少多少，rev(e).cap就增加多少，使得原来从u到v的一部分流量“退”了回去，而v到终点T的那部分被退回去的流量由新引进的起点S到v的流量代替，从而使得总流量增加

试想一下如果没有反向边想要实现这样的操作有多困难：要同时考虑两条路径的流量并加以控制，而反向边的存在使我们只要继续寻找增广路就好了。

 

Ford-Fulkerson算法就是上述算法的朴素实现：

#include <bits/stdc++.h>

using namespace std;
const int INF=1<<27;
int n,m,s,t;

int read()
{
    char ch;int num,f=0;
    while(!isdigit(ch=getchar())) f|=(ch=='-');
    num=ch-'0';
    while(isdigit(ch=getchar())) num=num*10+ch-'0';
    return f?-num:num;
}

struct edge
{
    int to,cap,rev;
};
vector<edge> a[10005];
bool vis[10005];

void add_edge(int x,int y,int c)
{
    a[x].push_back(edge{y,c,a[y].size()});  //用a[y].size()和a[x].size()-1来存放每条边反向边的位置
    a[y].push_back(edge{x,0,a[x].size()-1}); //一开始反向边的cap设为0
}

int dfs(int v,int t,int f)
{
    if(v==t) return f;
    vis[v]=true;
    for(int i=0;i<a[v].size();i++)
    {
        edge &e=a[v][i]; //这里使用引用的手法增强代码可读性
        if(!vis[e.to] && e.cap>0)
        {
            int d=dfs(e.to,t,min(f,e.cap));
            if(d>0) //找到一条增广路即返回其流量
            {
                e.cap-=d;
                a[e.to][e.rev].cap+=d;
                return d;
            }
        }
    }
    return 0;  //这里的return 0一定不能省，否则函数默认返回true,使得程序陷入死循环
}

int main()
{
    n=read();m=read();s=read();t=read();
    for(int i=1;i<=m;i++)
    {
        int x,y,c;
        x=read();y=read();c=read();
        add_edge(x,y,c);
    }
    
    int res=0;
    while(true)  //不断寻找增广路
    {
        memset(vis,0,sizeof(vis));
        int f=dfs(s,t,INF);
        if(!f) break;
        res+=f;
    }
    cout << res;
    return 0;
}

 

大部分注意点都已写在注释，有几点值得学习并要特别注意的

Tips：1、在存放u-->v的反向边时，选择存放其在vector[v]中的位置。这种同时记录另一点v以及一边在vector[v]中的位置的手法可以借鉴

          2、在遇到某个要经常表述的量字符长度太长时可以使用引用的方式缩短代码长度（&e=a[v][i]）

          3、如果返回类型为bool或int时，默认返回类型为1，最后的return false一定要加！

 

（2）Dinic算法

这种算法本质上和FF算法并没有什么不同，只是进行了一些优化

我们可以发现如果每次都直接dfs可能一开始会“绕弯路”，不能一步到位，而Dinic算法便能解决问题

 

Dinic算法每次都会对残余网络构造分层图，而在增广时每次只允许从level(n)走向level(n+1)。

也就是说Dinic算法保证每次增广都沿着当前的最短路，这样就避免了走弯路的情况。而当在残余网络已经不存在S到T的路径时，循环结束。

 

模板如下：

#include <bits/stdc++.h>

using namespace std;
const int INF=1<<27;
int n,m,s,t,level[10005],iter[10005];

int read()
{
    char ch;int num,f=0;
    while(!isdigit(ch=getchar())) f!=(ch=='-');
    num=ch-'0';
    while(isdigit(ch=getchar())) num=num*10+ch-'0';
    return f?-num:num;
}

struct edge
{
    int to,cap,rev;
};
vector<edge> a[10005];

void add_edge(int x,int y,int c)
{
    a[x].push_back(edge{y,c,a[y].size()});
    a[y].push_back(edge{x,0,a[x].size()-1});
}

void bfs(int s) //构建分层图
{
    memset(level,-1,sizeof(level));
    queue<int> q;
    level[s]=0;
    q.push(s);
    while(!q.empty())
    {
        int v=q.front();q.pop();
        for(int i=0;i<a[v].size();i++)
        {
            edge e=a[v][i];
            if(e.cap>0 && level[e.to]<0)
                level[e.to]=level[v]+1,q.push(e.to);
        }
    }
}

int dfs(int v,int t,int f) //与FF类似的增广过程
{
    if(v==t) return f;
    for(int &i=iter[v];i<a[v].size();i++)  //大大提高效率的当前弧优化
    {
        edge &e=a[v][i];
        if(level[e.to]==level[v]+1 && e.cap>0)  //增广时一定保证每步都走向下一层
        {
            int d=dfs(e.to,t,min(f,e.cap));
            if(d>0)
            {
                e.cap-=d;
                a[e.to][e.rev].cap+=d;
                return d;
            }
        }
    }
    return 0;
}

int main()
{
    n=read();m=read();s=read();t=read();
    for(int i=1;i<=m;i++)
    {
        int x,y,c;x=read();y=read();c=read();
        add_edge(x,y,c);
    }
    
    int res=0;
    while(true)
    {
        memset(iter,0,sizeof(iter)); //注意对当前弧优化数组的初始化位置
        bfs(s);
        if(level[t]<0) break; //已不存在增广路
        int f;
        while((f=dfs(s,t,INF))>0) res+=f;
    }
    cout << res;
    return 0;
}

 

可以看到有一个特殊的iter数组，这就是当前弧优化的数组

for(int &i=iter[v];i<a[v].size();i++)

这样可以保证当再次遇到v点时，不会将之前已经走“满”的出路再走一遍，而是从第iter[v]条出路开始走。

在我个人看来这种手法与记忆化搜索是同种思想，将不可能的路径或是已经得出结果的路径进行标记和存储

注意这里的i是引用，同时iter数组在每次重新构建分层图后要初始化

 

if(d>0)
{
      e.cap-=d;
      a[e.to][e.rev].cap+=d;
      return d;
}

这里可以选择不直接返回，而是将f-=d,ret+=d。在递归结束前返回ret即可。

经过检验，这两种耗时相近，没有显著优化。

 

2、费用流算法

最小费用最大流模板题：https://www.luogu.org/problemnew/show/P3381

以下模板以此题为准

 

对于最小费用最大流，我们只要在最大流的基础上每次增广最短的路径即可。

 

证明如下：

首先，假设流f是最小费用流，那么此时残余网络必定不可能有负圈，否则可以在不改变流量的情况下减少费用

因此，f是最小费用流，此时残余网络必定不可能有负圈，反之亦然。

 数学归纳法：

1、流量为0的流f（0）是流量为0的最小费用流

2、假设流量为i的流f（i）是最小费用流，并且求出了流量为i+1的流f（i+1），那么此时f(i+1)-f(i)就是f(i)的残余网络中的最短路

3、假设f(i+1)不是最小费用流，则存在f'(i+1)比f(i+1)的费用小。因为f'(i+1)-f(i)除S和T外各点流入流出量相同，所以f'(i+1)-f(i)由一条路径和几个圈组成。又因为f'(i+1)的费用比f(i+1)少，而f(i+1)-f(i)是f(i)的残余网络的最短路径，所以f'(i+1)-f(i)有负圈。

4、f'(i+1)-f(i)被包含于f(i)的残余网络中，所以f(i)中有负圈，这与假设f(i)是最小费用流相矛盾，因此f(i+1)是最小费用流。

因此，对于任意的i，f(i)均为最小费用流。

 

由于图中有负边权，因此一般只能使用Bellman-ford或者SPFA求最短路

但是借助为每个顶点设置的势h(v)我们可以用dijkastra来求出最短路，并将原本复杂度中的|V|变为了log|V|。

由于对于每条边edge(u,v)都有如下性质：(S到v的最短距离)<=（S到u的最短距离）+weight(u,v)

因此将每个顶点的势h(v) 设置为S到v的最短距离就使得新的边权weight''(u,v)=weight(u,v)+h(u)-h(v)>=0，从而用dijkastra求最短路

 

代码如下：

#include <bits/stdc++.h>

using namespace std;
const int MAXN=5005;
const int INF=1<<27;
typedef pair<int,int> P;
int n,m,s,t;

int read()
{
    char ch;int num,f=0;
    while(!isdigit(ch=getchar())) f|=(ch=='-');
    num=ch-'0';
    while(isdigit(ch=getchar())) num=num*10+ch-'0';
    return f?-num:num;
}

struct edge
{
    int to,cap,cost,rev;
};
vector<edge> a[MAXN];
int h[MAXN],dist[MAXN],preV[MAXN],preE[MAXN];

void add_edge(int from,int to,int cap,int cost)
{
    a[from].push_back(edge{to,cap,cost,a[to].size()});
    a[to].push_back(edge{from,0,-cost,a[from].size()-1});
}

void min_cost_flow(int x,int t,int f)
{
    int maxf=0,minc=0;
    memset(h,0,sizeof(h));
    while(f>0)  //Dijkasta求最短路
    {
        priority_queue<P,vector<P>,greater<P> > que;  //堆优化
        fill(dist,dist+n+1,INF);
        dist[s]=0;
        que.push(P(0,s));
        while(!que.empty())
        {
            P p=que.top();que.pop();
            int v=p.second;
            if(dist[v]<p.first) continue;
            
            for(int i=0;i<a[v].size();i++)
            {
                edge &e=a[v][i];
                if(e.cap>0 && dist[e.to] > dist[v]+e.cost+h[v]-h[e.to])  //松弛
                {
                    dist[e.to]=dist[v]+e.cost+h[v]-h[e.to];
                    preV[e.to]=v; //记录前一个点以及边在a[v]中的位置
                    preE[e.to]=i;
                    que.push(P(dist[e.to],e.to));
                }
            }
        }
        if(dist[t]==INF) break;
        
        for(int i=1;i<=n;i++) h[i]+=dist[i];  //对势进行更新
        
        int d=f;
        for(int i=t;i!=s;i=preV[i])  //顺藤摸瓜，由T沿路径回到S
            d=min(d,a[preV[i]][preE[i]].cap);
        f-=d;minc+=d*h[t];maxf+=d;
        for(int i=t;i!=s;i=preV[i])
        {
            edge &e=a[preV[i]][preE[i]];
            e.cap-=d;
            a[i][e.rev].cap+=d;
        }
    }
    cout << maxf << " " << minc;
}

int main()
{
    n=read();m=read();s=read();t=read();
    for(int i=1;i<=m;i++)
    {
        int from,to,cap,cost;
        from=read();to=read();cap=read();cost=read();
        add_edge(from,to,cap,cost);
    }
    
    min_cost_flow(s,t,INF);
    return 0;
}

 

这里最难理解的操作应该就是势的更新了

for(int i=1;i<=n;i++) h[i]+=dist[i];

由于前后相消，因此dist[v]=sigma(e.cost)+h(S)-h(v).

时刻记住h(v)的定义：在旧边权的图中S到v的最短距离   ，   以及dist[v]的含义：在新边权的图中的最短距离

因此h(S)=0，而sigma(e.cost)就是新的更新后的h'(v)

所以h'(v)=h(v)+dist[v]

 

Tips:

1、按照我的理解，这里对势的构造和差分约束的思想类似，通过边的性质构造非负性：(S到v的最短距离)<=（S到u的最短距离）+weight(u,v)

2、这里记录路径的方式同样可以借鉴，用到了前面记录反向边的方法

 

至于各类网络流经典建模的问题，就放到下次总结吧。

寒假要抓紧先把所有省选知识点都学完啊。

推荐阅读