网络流之dinic

网络流

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

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

用上图为例。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找呢，得到的一定是正解吗？当然不一定。

以下图为例。

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

那么怎么办呢，是不是选择了就没办法反悔了？

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

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

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

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

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

然后无路可走，结束。

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

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算法有三种优化方法。

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

考虑下面这个图

对于顶点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

溜～