最大流问题

问题描述

• 最大流：使得整个流网络流量之和最大的流的安排

最大流最小割定理

• 判定定理：
• 可行流$f$是最大值
• 可行流$f$的残留网络中不存在增光路
• 存在某个割$(S, T)$，使$|f| = c(S, T)$
• 使用方法：
• 维护一个针对流$f$的残留网络，如果不存在增广路，则流$f$为最大流（最大可行流）

Edmonds-Karp (EK) 算法

• 核心思想：让一股流沿着增广路经从源点流向汇点，然后不断更新最大流量值，直到网络上不存在增广路经为止

• 实现过程：BFS寻找增广路经。在残留流量值大于0的边中，找到一条从源点到汇点的路径，并且计算路径上每条边残留流量值的最小值$f_{min}$，则网络的最大流量就可以增加$f_{min}$（正向边容量值减$f_{min}$，反向边加$f_{min}$）

• 邻接表存储技巧：正反成对存储，如2和3，4和5。

• 目的：更新边的流量时可以用xor 1的方式找到对应的正向边或反向边

• 时间复杂度：$O(nm^2)$

• 模板代码（洛谷P3376）

#include <iostream>
#include <queue>

const int N = 200 + 5, M = 5000 * 2 + 5, PosInf = 1e9;

int n, m, s, t;
long long ans, fmin[M];
int head[M], count = 1, prev[M], addedAt[M][M];
bool vis[M];

struct Edge
{
    int to, next;
    long long f;
}edges[M];

void Init()
{
    for (int i = 0; i < M; i++)
        head[i] = -1;
} 

void Add(int u, int v, long long w)
{
    // 建正向边 
    edges[++count].to = v;
    edges[count].f = w;
    edges[count].next = head[u];
    head[u] = count;

    // 建反向边 
    edges[++count].to = u;
    edges[count].f = 0;
    edges[count].next = head[v];
    head[v] = count;
}

bool Search()
{
    for (int i = 1; i <= n; i++)
        vis[i] = false;

    std::queue<int> q;
    q.push(s);
    vis[s] = true;
    fmin[s] = PosInf;

    while (!q.empty())
    {
        int now = q.front();
        q.pop();

        for (int i = head[now]; i != -1; i = edges[i].next)
        {
            if (edges[i].f == 0)
                continue;
            int v = edges[i].to;
            if (vis[v] == true)
                continue;
            vis[v] = true;

            fmin[v] = std::min(fmin[now], edges[i].f);
            prev[v] = i;

            q.push(v);

            if (v == t)
                return true;
        }
    }
    return false;
}

void UpdateEdges() // 更新每一条边 
{
    int pos = t;
    while (pos != s)
    {
        int v = prev[pos];
        edges[v].f -= fmin[t];
        edges[v ^ 1].f += fmin[t];
        pos = edges[v ^ 1].to;
    }
    ans += fmin[t];
}

int main()
{
    Init();
    std::cin >> n >> m >> s >> t;
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        long long w;
        std::cin >> u >> v >> w;
        if (addedAt[u][v] == 0) // 处理重边，实际上不处理也可以AC，删掉addAt相关的代码即可
        {
            Add(u, v, w);
            addedAt[u][v] = count;
        }
        else
        {
            edges[addedAt[u][v] - 1].f += w;
        }
    }

    while (Search())
    {
        UpdateEdges();
    }

    std::cout << ans << std::endl; 
    return 0;
}

Dinic 算法

• 由EK算法产生的问题：EK算法一次只会找一条增广路，但实际上一个流网络不一定只有一条增广路

• Dinic算法的解决思路：用暴力搜索的方式，把能够增广的路径全部增广一次

• 这样优化的问题：图上可能有环，导致死循环

  • 解决思路：引入分层图的概念。即把图分为一层又一层，每次增广时，只允许从上一层走向下一层，防止在环里打转转
  • 层数：从源点到当前点的BFS层数
  • 实现思路：先从源点BFS一次，建分层图；再DFS（没有回溯，只会一路走到黑），搜索出所有可以增广的路径，然后统一搜索一遍
  • 时间复杂度：$O(n^2m)$
  • 当前弧优化：在每个点记录从源点到这里最多能流多少流量，搜索时枚举这个点到汇点的最大流量，判断如果要走的某条边已经满了，下一次来的时候就跳过了
  • 注意：如果优化不好，很容易超时
  • 模板代码（洛谷P3376）

#include <iostream>
#include <queue>
#include <cstring>

const int N = 205, M = 5000 * 2 + 5, PosInf = 1e9;

int n, m, start, finish;
int head[N], count;
int q[N], dis[N], current[N]; // current: 用于当前弧优化 

struct Edge
{
    int to, c;
    long long next;
}edges[M];

void Add(int a, int b, long long c)
{
    edges[count].to = b;
    edges[count].c = c;
    edges[count].next = head[a];
    head[a] = count++;

    edges[count].to = a;
    edges[count].c = 0;
    edges[count].next = head[b];
    head[b] = count++;
}

bool BfsLayering()
{
    std::queue<int> q;
    memset(dis, -1, sizeof dis);
    q.push(start);
    dis[start] = 0;
    current[start] = head[start];
    while (!q.empty())
    {
        int now = q.front();
        q.pop();
        for (int i = head[now]; i != -1; i = edges[i].next)
        {
            int v = edges[i].to;
            if (dis[v] == -1 && edges[i].c > 0)
            {
                dis[v] = dis[now] + 1;
                current[v] = head[v];
                if (v == finish)
                    return true;
                q.push(v);
            }
        }
    }
    return false;
}

long long Find(int u, int limit)
{
    if (u == finish)    return limit;
    int flow = 0;
    for (int i = current[u]; i != -1 && flow < limit; i = edges[i].next)
    {
        current[u] = i; // 当前弧优化
        int v = edges[i].to; 
        if (dis[v] == dis[u] + 1 && edges[i].c)
        {
            long long t = Find(v, std::min(edges[i].c, limit - flow));
            if (!t) dis[v] = -1; // 到不了终点的点删掉，把层数设置为-1
            edges[i].c -= t;
            edges[i ^ 1].c += t;
            flow += t; 
        }
    }
    return flow;
}

long long Dinic()
{
    long long r = 0, flow;
    while (BfsLayering()) // BfsLayering() == true: 有增广路 
        while (flow = Find(start, PosInf))
            r += flow;
    return r;
}

int main()
{
    std::cin >> n >> m >> start >> finish;
    memset(head, -1, sizeof head);
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        long long w;
        std::cin >> u >> v >> w;
        Add(u, v, w);
    }

    std::cout << Dinic() << std::endl;
    return 0;
}

本题代码

• 使用Dinic算法 + 当前弧优化

#include <iostream>
#include <queue>
#include <cstring>

const int N = 10005, M = 100000 * 2 + 5, PosInf = 1e9;

int n, m, start, finish;
int head[N], count;
int q[N], dis[N], current[N]; // current: 用于当前弧优化 

struct Edge
{
    int to, c;
    int next;
}edges[M];

void Add(int a, int b, int c)
{
    edges[count].to = b;
    edges[count].c = c;
    edges[count].next = head[a];
    head[a] = count++;

    edges[count].to = a;
    edges[count].c = 0;
    edges[count].next = head[b];
    head[b] = count++;
}

bool BfsLayering()
{
    std::queue<int> q;
    memset(dis, -1, sizeof dis);
    q.push(start);
    dis[start] = 0;
    current[start] = head[start];
    while (!q.empty())
    {
        int now = q.front();
        q.pop();
        for (int i = head[now]; i != -1; i = edges[i].next)
        {
            int v = edges[i].to;
            if (dis[v] == -1 && edges[i].c)
            {
                dis[v] = dis[now] + 1;
                current[v] = head[v];
                if (v == finish)
                    return true;
                q.push(v);
            }
        }
    }
    return false;
}

int Find(int u, int limit)
{
    if (u == finish)    return limit;
    int flow = 0;
    for (int i = current[u]; i != -1 && flow < limit; i = edges[i].next)
    {
        current[u] = i; // 当前弧优化
        int v = edges[i].to; 
        if (dis[v] == dis[u] + 1 && edges[i].c)
        {
            int t = Find(v, std::min(edges[i].c, limit - flow));
            if (!t) dis[v] = -1; // 到不了终点的点删掉，把层数设置为-1
            edges[i].c -= t;
            edges[i ^ 1].c += t;
            flow += t; 
        }
    }
    return flow;
}

int Dinic()
{
    int r = 0, flow;
    while (BfsLayering()) // BfsLayering() == true: 有增广路 
        while (flow = Find(start, PosInf))
            r += flow;
    return r;
}

int main()
{
    std::cin >> n >> m >> start >> finish;
    memset(head, -1, sizeof head);
    for (int i = 1; i <= m; i++)
    {
        int a, b, c;
        std::cin >> a >> b >> c;
        Add(a, b, c);
    }

    std::cout << Dinic() << std::endl;
    return 0;
}