网络流

有一个有向图,存在源点s和汇点e,中间还有一些其他的顶点,所有的点用有向边连接起来。边的权值所代表的是这一条边所能通过的最大流量。问从源点到汇点最大能通过多少流量。

就好像是一个很多有向的水管将一些点连接了起来,源点s有无穷无尽的水流,最后在e点能够通过多大的流量。

1

用上图为例。s-3-5-e这一条路径可以流10的流量,s-2-3-5-e这条路径可以流5的流量,s-2-4-e可以流10的流量,所以最后e点可以流通25的流量。

这样的问题被称之为最大流问题。

增广路

从上面的例子可以发现,求解最大流问题,就是寻找从s到e的路径,且路径的每一条边都还有空间(就是管子还没被水流完全占满,即边的权值不为0),那么这一条路径可以贡献flow = min(路径所有边的权值)的流量。并且这条路径上所有的边的权值减少flow那么多。直到找不到这样的路径为止。

上述的路径被称之为增广路,即一条可以为汇点增加流量的路径。

那么求解最大流问题就是不断寻找增广路的问题。

那么问题来了,寻找增广路是不是可以xjb找呢,得到的一定是正解吗?当然不一定。

以下图为例。

1

先走s-2-3-5-e这一条增广路,增加了15的流量,再走s-2-4-e这一条路,增加5的流量,然后就无路可走了,这时候得到的结果为20,明显不对。

那么怎么办呢,是不是选择了就没办法反悔了?

我们考虑为每一条边加一条反边,初始化权值为0,意味着流量为0,所以一开始构建好的图是下面这个样子的,红色的边是反边。

2

当我们找到一条增广路的时候,这一条增广路的所有边权都要减去贡献的flow,而这条路径的所有反边都要加上flow,这样就达到了反悔的效果。

下面来看看反边具体有什么用吧。

还是用刚刚的图为例,先走s-2-3-5-e这一条增广路,增加15的流量,得到下面的情况。

3

然后走s-3-2-4-e这一条增广路,增加了10的流量,得到下图的情况

4

然后无路可走,结束。

可以发现反边达到了反悔的效果,即使我们一开始走的不是最优的顺序,也可以通过反边反悔最后得到正解。

dinic

dinic算法是求解最大流问题的常用算法之一。

dinic将图进行了分层,其实就是用bfs对图进行遍历,为每个顶点标深度。比如上图的s深度为1,顶点2和3深度为2,顶点4和5深度为3,e的深度为4。

dinic规定,在寻找增广路的时候,我们只能走这样的边<u, v>满足顶点v的深度比顶点u的深度大1

寻找增广路是通过dfs来寻找的,所以dinic算法就是由bfs和dfs组合。

模板

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int maxn = 1e6+5;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;

// 用链式前向星来存储图
struct ed
{
    int to, val, ne;
}edge[maxn<<1];
int head[maxn], dep[maxn];
// 顶点数n,边数m,源点s,汇点e,加边时的指针tot
int n, m, s, e, tot;

void init()
{
    tot = -1;
    memset(head, -1, sizeof(head));
}

void addEdge(int u, int v, int val)
{
    edge[++tot].to = v;
    edge[tot].val = val;
    edge[tot].ne = head[u];
    head[u] = tot;
}

// 就是最普通的bfs
int bfs()
{
    memset(dep, -1, sizeof(dep));
    dep[s] = 0;
    queue<int> q;
    q.push(s);
    while(!q.empty())
    { 
        int u = q.front();
        q.pop();
        for(int i=head[u]; ~i; i=edge[i].ne)
        {
            int v = edge[i].to;
            if(dep[v]==-1 && edge[i].val>0) //若这条边还有流量,我们才能走到顶点v,所以才更新v的深度
            {
                dep[v] = dep[u]+1;
                q.push(v);
            }
        }
    }
    return (dep[e] != -1); //若dep[e]==-1则表示没有可以到达e的增广路了,算法结束。
}

// 当前顶点u,当前流量flow
// 初始时dfs(s, inf)
int dfs(int u, int flow)
{
    // 若当前到达了e,则返回当前flow值
    if(u == e)return flow;
    for(int i=head[u]; ~i; i=edge[i].ne)
    {
        int v = edge[i].to;
        // 若顶点v的深度比u大一,且边<u, v>还有流量
        if(dep[v]==dep[u]+1 && edge[i].val)
        {
            // 递归继续寻找,注意min操作,要传递最小的边权
            int a = dfs(v, min(flow, edge[i].val));
            if(a>0) //若找到增广路
            {
                edge[i].val -= a; // 更新正向边和反边的权值
                edge[i^1].val += a;
                return a;
            }        
        }
    }
    // 若最后没找到增广路,则返回0
    return 0;
}

ll dinic()
{
    ll ans = 0;
    // 不断地bfs,直到没有增广路
    while(bfs())
    {
        // 找到一条增广路,并且得到这条路能够贡献的流量a。1<<30表示无穷大
        int a = dfs(s, (1<<30));
        ans += a;
    }
    return ans;
}

int main()
{
    scanf("%d%d%d%d", &n, &m, &s, &e);
    init();
    for(int i=1;i<=m;i++)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        addEdge(u, v, w);
        addEdge(v, u, 0); //反边
    }
    printf("%lld\n", dinic());
    return 0;
}

dinic的优化

dinic算法有三种优化方法。

  • 当前弧优化
  • 多路增广
  • 炸点

考虑下面这个图

5

对于顶点4来说,我们一开始可以从s-3-4这样过去,然后我们可以对4-6-e这边贡献30的流量,按照上述的dinic算法,这时候我们就结束一次dfs了,然后又进行bfs再继续dfs。这样其实做了很多冗余的工作,因为我们发现从s-3-4还剩余20的流量可以走4-5-e,这样可以减少bfs和dfs的次数,这种优化方法被称为多路增广

这个时候4-6-e这条路径的流量已经为0了,但是我们从s-2-4这条路径到达顶点4时,我们还是会从头开始遍历与顶点4相连的边,所以还是会从<4, 6>开始遍历,对于稠密图来说,这里做了很多无用功,如果我们能知道要从上一次增广的边开始(这里是<4, 5>),就能够减少这种无用功,这种优化方法被称为当前弧优化

若在某次dfs的时候,我们发现已经无法通过某个点继续增加流量了,我们就把这个点“去掉”,那么当前dfs就不会再次进入到这个点,这种优化方式被称之为炸点

模板

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int maxn = 1e6+5;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;

struct ed
{
    int to, val, ne;
}edge[maxn<<1];
int head[maxn],dep[maxn], cur[maxn];
int n, m, s, e, tot;

void init()
{
    tot = -1;
    memset(head, -1, sizeof(head));
}

void addEdge(int u, int v, int val)
{
    edge[++tot].to = v;
    edge[tot].val = val;
    edge[tot].ne = head[u];
    head[u] = tot;
}

int bfs()
{
    memset(dep, -1, sizeof(dep));
    dep[s] = 0;
    queue<int> q;
    q.push(s);
    while(!q.empty())
    { 
        int u = q.front();
        q.pop();
        for(int i=head[u]; ~i; i=edge[i].ne)
        {
            int v = edge[i].to;
            if(dep[v]==-1 && edge[i].val>0)
            {
                dep[v] = dep[u]+1;
                q.push(v);
            }
        }
    }
    return (dep[e] != -1);
}

int dfs(int u, int flow)
{
    if(u == e)return flow;
    // rflow用于多路增广,表示流入到顶点u的剩余未流出的流量
    int rflow = flow;
    // 当前弧优化,通过引用,可以改变cur[i]的值,使得下次遍历到顶点u时,会直接从上次增广的边开始遍历
    for(int& i=cur[u]; ~i; i=edge[i].ne)
    {
        int v = edge[i].to;
        if(dep[v]==dep[u]+1 && edge[i].val)
        {
            int a = dfs(v, min(rflow, edge[i].val));
            edge[i].val -= a;
            edge[i^1].val += a;
            rflow -= a; // 剩余流量要减少
            if(rflow<=0)break; // 若没有剩余流量了,就break
        }
    }
    // 若没有一丝流量流出,则表示通过顶点u已经无法增广了,于是炸点,dep可以设置为任何无意义值
    if(rflow == flow)
        dep[u] = -2;
    return flow - rflow; // 返回流出的流量
}

ll dinic()
{
    ll ans = 0;
    while(bfs())
    {
        // 新一轮dfs之前要对cur进行初始化
        for(int i=1;i<=n;i++)cur[i] = head[i];
        int a = dfs(s, (1<<30));
        ans += a;
    }
    return ans;
}

int main()
{
    scanf("%d%d%d%d", &n, &m, &s, &e);
    init();
    for(int i=1;i<=m;i++)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        addEdge(u, v, w);
        addEdge(v, u, 0);
    }
    printf("%lld\n", dinic());
    return 0;
}

END

溜~