网络流问题

最大流

Ford-Fulkerson算法

概述

最大流问题中，我们主要关注剩余容量。在获得最后各边的剩余容量之后，只需要拿源点的初始容量减去剩余容量即可得到流量。

我们首先寻找一条能抵达汇点的路径，很容易得到该路径能输送的最大流量取决于这条路径最小容量的边。然后将这条路径加上该流量，更新剩余容量。当某条边剩余流量为0时我们将无法再通过它来输送流量，所以可以考虑将其移除，之后再寻找其他路径，直至无法抵达汇点。我们将这个过程中删除满流的边之后，边权为剩余流量的图称为残量网络。

但是这个过程中无法进行回溯，所以如果我们删除了一条不是最优的边(表示选中了它)那我们将无法放弃选择，从而得不到最优解。Ford−FulkersonFord-Fulkerson算法的关键在于，当我们在压入流量的同时在残量网络中添加容量大小与正向流量相等的反向边。

例如：对于节点v1−>v2v1->v2如果v1v1流向v2v2的容量为6，流量大小为5那么我们添加一条容量(剩余容量)为5的反向边(如果已经存在反向边则更新其容量)。最终不存在路径可达汇点。

实现思路

  1. 找到一条可达汇点的路径(增广路径)并获得该路径下最小容量cc(最大流量)
  2. 将该路径下所有边减去cc，添加对应反向边；同时ansans加cc；
  3. 重复上述操作直至无路径可达汇点；

示例代码

修改后的BFSBFS，寻找增广路径。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
bool bfs(int i, int t)
{
    c.clear();
    c.resize(110, MAX);//存放最大流量
    path.clear();
    path.resize(110, -1);
    path[i] = -1;//路径，前缀节点
    queue<int> q;
    q.push(i);
    visited.clear();
    visited.resize(110, false);
    visited[i] = true;
    while (!q.empty())
    {
        int x = q.front();
        q.pop();
        map<int, long long>::iterator iter;
        for (iter = last[x].begin(); iter != last[x].end(); iter++)
        {
            if ((!visited[iter->first]) && (iter->second > 0))
            {
                q.push(iter->first);
                path[iter->first] = x;
                visited[iter->first] = true;
                c[iter->first] = min(iter->second, c[x]);//更新最小流量
                if (iter->first == t)
                {
                    return true;
                }
            }
        }
    }
    return false;
}

核心代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void FordFulker(int n, int s, int t)
{
    long long ans = 0;
    while (bfs(s, t))
    {
        for (int i = t; i != s; i = path[i])
        {
            int pre = path[i];
            last[pre][i] -= c[t];
            last[i][pre] += c[t];
        }
        ans += c[t];
    }
    cout << ans << endl;
}

Edmonds-Karp算法

概述

好像上面写的就是EKEK算法？与FFFF区别就是EKEK只选择最短的增广路径也就是使用BFSBFS

Dinic算法

概述

DinicDinic算法实际上就是对EKEK算法的优化，具体有四点优化：

  1. 搜索顺序优化：根据bfsbfs建立分层图，每次dfsdfs只“向下”搜索，对于同一层的点不进行进一步搜索，避免来回递归；
  2. 当前弧优化：在dfsdfs的过程中如果我们第二次遇到了节点uu那么我们不必再从与uu相连的第一条边开始遍历，而是从第一次遇到uu之后的遍历到的边开始。这是因为在第一次遇到uu的时候我们遍历到第ii条边才开始继续递归，这说明前i−1i-1条边都已经无法继续给汇点输送流量了；
  3. 无用点优化：如果在dfsdfs过程中某个点返回的可用流量小于等于0，代表该点无法再输送流量，在之后遍历过程中不再考虑该点(深度设为0)；
  4. 剩余容量优化：某条增广路径的可输送容量满了则不再继续遍历后续边；

实现思路

  1. bfsbfs建立分层图并初始化当前弧数组cur[]cur[]；
  2. dfsdfs搜索增广路径；
  3. 重复上述操作并不断增加ansans；

示例代码

bfsbfs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
bool bfs(int i, int t)
{
    memset(depth, 0, sizeof(depth));
    queue<int> q;
    q.push(i);
    depth[i] = 1;
    cur[i] = 0;
    while (!q.empty())
    {
        int x = q.front();
        q.pop();
        map<int, long long>::iterator iter;
        for (iter = last[x].begin(); iter != last[x].end(); iter++)
        {
            if ((!depth[iter->first]) && (iter->second > 0))
            {
                q.push(iter->first);
                depth[iter->first] = depth[x] + 1;
                cur[iter->first] = 0;
                if (iter->first == t)
                {
                    return true;
                }
            }
        }
    }
    return false;
}
dfsdfs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
long long dfs(int u, int t, long long limit)
{
    if (u == t)
    {
        return limit;
    }
    long long mid = limit;
    map<int, long long>::iterator iter;
    for (iter = next(last[u].begin(), cur[u]); iter != last[u].end(); iter++)
    {
        if (iter->second > 0 && depth[iter->first] == depth[u] + 1)
        {
            long long tmp = dfs(iter->first, t, min(mid, iter->second));
            if (tmp <= 0)//无用点优化
            {
                depth[iter->first] = 0;
            }
            mid -= tmp;
            iter->second -= tmp;         // 可流出量减少
            last[iter->first][u] += tmp; // 反向边增加
            if (mid <= 0)//剩余容量优化
            {
                break;
            }
        }
        cur[u]++;//当前弧优化，表示对于节点u我们已经遍历到了第cur[u]条边(关键优化)
    }
    return limit - mid;
}
Dinic
1
2
3
4
5
6
7
8
9
10
void Dinic(int n, int s, int t)
{
    long long ans = 0;
    while (bfs(s, t))
    {
        ans += dfs(s, t, MAX);
    }

    cout << ans << endl;
}

ISAP算法

概述

在DinicDinic算法中我们每次增广完都要重新BFSBFS，而在ISAPISAP算法中我们选择从tt(汇点)进行一次BFSBFS后，每次在增广过程中就完成分层。并且使用一个数组grp[]grp[]来记录各层存在的节点数，当某一层节点数为0时说明出现断层，直接跳出循环。

实现思路

  1. 从汇点开始BFSBFS；
  2. DFSDFS搜索增广路径，当前节点所有边都搜索完之后当前节点深度加一；
  3. 重复上述操作直至出现断层；

示例代码

BFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;
#define MAX 2147483647
map<int, map<int, long long>> last;
int depth[510];
int gap[510];  // 记录每层有多少点
int cur[1010]; // 当前弧数组
bool bfs(int i, int t)
{
    memset(depth, -1, sizeof(depth));//好像必须设为-1
    queue<int> q;
    q.push(i);
    depth[i] = 0;
    gap[depth[i]]++;//如果前面从0开始这里会出问题
    cur[i]=0;
    //俺也不知道为啥
    while (!q.empty())
    {
        int x = q.front();
        q.pop();
        map<int, long long>::iterator iter;
        for (iter = last[x].begin(); iter != last[x].end(); iter++)
        {
            if ((depth[iter->first] < 0) && (iter->second >= 0))//建图的时已经为每条边加一条容量为0的反向边
            {
                q.push(iter->first);
                depth[iter->first] = depth[x] + 1;
                gap[depth[iter->first]]++;
                cur[iter->first] = 0;
            }
        }
    }
    return false;
}
BFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
long long dfs(int u, int t, long long limit, int s, int n)
{
    if (u == t)
    {
        return limit;
    }
    long long mid = limit;
    map<int, long long>::iterator iter;
    for (iter = next(last[u].begin(), cur[u]); iter != last[u].end(); iter++)
    {
        if (iter->second > 0 && depth[iter->first] + 1 == depth[u])
        {
            long long tmp = dfs(iter->first, t, min(mid, iter->second), s, n);
            if (tmp)
            {
                mid -= tmp;
                iter->second -= tmp;         // 可流出量减少
                last[iter->first][u] += tmp; // 反向边增加
                if (mid <= 0)
                {
                    return limit;
                }
            }
        }
        cur[u]++; // 当前弧优化，表示对于节点u我们已经遍历到了第cur[u]条边
    }
    gap[depth[u]]--;
    if (gap[depth[u]] == 0) // 出现断层
        depth[s] = n + 1;
    depth[u]++;//当前节点深度增加
    gap[depth[u]]++;

    return limit - mid;
}
ISAP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void ISAP(int n, int s, int t)
{
    long long ans = 0;
    bfs(t, s);
    while (depth[s] <= n)
    {
        for (int i = 1; i <= n; i++)
        {
            cur[i] = 0;
        }
        ans += dfs(s, t, MAX, s, n);
    }
    cout << ans << endl;
}

最小割

概述

割

对于一个图G(V,E)G(V,E)，其割定义为一种图的划分：将所有点划分为SS和T=V−ST=V-S两个集合，其中源点∈S源点\in S，汇点∈T汇点\in T。

割的容量

定义为所有从SS到TT的边容量之和。最小割指的是求一个割使得割的容量最小。

最大流最小割定理

对于任意网络，其上的最大流的值等于最小割的容量。