学习笔记

网络流毒瘤

网络流

基本概念

（from OIwiki）

网络：有向图 G=(V,E)G = (V, E)，其中每条边有一个流量 cc，当 (u,v)∉E(u, v) \notin E 时，c(u,v)=0c_{(u, v)} = 0。其中有两个特殊的点：源点 s∈Vs \in V，t∈Vt \in V。

流：定义函数 f(u,v)f(u, v)，满足下列条件：

  1. 容量限制：f(u,v)≤c(u,v)f(u, v) \le c(u, v)。
  2. 斜对称性：f(u,v)=−f(v,u)f(u, v) = -f(v, u)。
  3. 流守恒性：∀x∈V−{s,t},∑(s,x)∈Ef(u,x)=∑(x,v)∈Ef(x,v)\forall x\in V-\{ s, t\}, \sum_{(s,x)\in E} f(u, x)=\sum _{(x,v)\in E} f(x,v)

最大流

定义：有一张网络，要求从 ss 到 tt 的最大流量。

剩余容量：对于边 (u,v)(u, v)，剩余容量为 c(u,v)−f(u,v)c(u, v) - f(u, v)。

残量网络：将 GG 中所有点和所有剩余容量大于 00 的边构成的子图称为残量网络。

增广路：从源点到汇点的路径。

可以证明，当残量网络中没有增广路存在时，网络达到最大流。

Dinic 算法

分层图：GL=(V,EL),EL={(u,v)∣dv=du+1}G_L = (V, E_L),E_L=\{(u, v)|d_v=d_u+1\} 的图。

阻塞流：在分层图 GLG_L 中找到的最大的增广流，使得仅在 GLG_L 上无法找到更大的增广流。

算法流程：先在残量网络中 bfs 一遍，构造出分层图。再在分层图上 dfs 出阻塞流。循环这个过程直至残量网络无法找到增广路。

当前弧优化：在 dfs 的过程中，及时将已经扩展完的边或者是无法扩展的边从图中删去。

代码实现：

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#define LOCAL
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 1e5 + 10;
const ll INF = 1e17;
int h[N], e[N], ne[N], w[N], idx;
int now[N], d[N];
int n, m;
ll flow, maxflow;

inline void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
    e[idx] = a, w[idx] = 0, ne[idx] = h[b], h[b] = idx ++;
}

queue<int> q;
bool bfs()
{
    memset(d, 0, sizeof d);
    while(q.size()) q.pop();
    d[1] = 1;
    now[1] = h[1];
    q.push(1);
    while(q.size())
    {
        int u = q.front();
        q.pop();

        for(int i = h[u]; i != -1; i = ne[i])
        {
            int v = e[i];
            if(!d[v] && w[i])
            {
                d[v] = d[u] + 1;
                now[v] = h[v];
                q.push(v);
                if(v == n) return true;
            }
        }
    }
    return false;
}

ll dinic(int x, ll flow)
{
    if(x == n) return flow;
    ll rest = flow, k;
    int i;
    for(i = now[x]; i != -1; i = ne[i])
    {
        now[x] = i; //  当前弧优化
        int v = e[i];
        if(d[v] == d[x] + 1 && w[i])
        {
            k = dinic(v, min((ll)w[i], rest));
            if(!k) d[v] = 0;
            w[i] -= k;
            w[i ^ 1] += k;
            rest -= k;
        }
    }
    return flow - rest;
}

// in main
while(bfs())
    while(flow = dinic(1, INF))
        maxflow += flow;
    
cout << maxflow << endl;

HLPP 算法 预流推进

上面的 Dinic 算法时间复杂度为 O(n2m)O(n^2m)，一般情况下表现良好。但是当图的规模增加时，则需要复杂度更小的算法。HLPP 的算法为 O(n2m)O(n^2\sqrt m)。

在 HLPP 算法中，每个节点引入了高度的概念，为汇点到该点的距离。同时每个点上存储了一个溢出值，当向下推流时，先将流量储存在该点中，以便后面的搜索。

算法流程：

  1. BFS 出每个节点的高度。
  2. 从源点开始搜索，将与 s 相连的边跑到满流，多出的流使得这些点溢出，放入优先队列。
  3. 按从高到低更新每个节点，把溢出节点放入优先队列。
  4. 如果该节点无法找到合法路径且还有溢出流量，把它的高度提升到它邻居的最低值加一。
  5. 重复 3、4，直至没有溢出节点。

GAP 优化：当高度出现断层时，该高度以上的节点都无法进行流量的更新，则让这些点高度全部变为 n+1n+1，以便推送回 ss。

代码实现：

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#define LOCAL
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10, INF = 2147483647;
int h[N], e[N], ne[N], w[N], idx;
int dep[N], flow[N], gap[N];
int n, m, s, t;

inline void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
    e[idx] = a, w[idx] = 0, ne[idx] = h[b], h[b] = idx ++;
}

bool is_in[N], is[N];
bool bfs()
{
    for(int i = 1; i <= n; i ++ ) dep[i] = INF;
    dep[t] = 0;
    queue<int> q;
    q.push(t);
    is[t] = true;
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        is[u] = false;
        for(int i = h[u]; i != -1; i = ne[i])
        {
            int v = e[i];
            if(w[i] || dep[v] <= dep[u] + 1) continue;
            dep[v] = dep[u] + 1;
            if(!is[v])
            {
                q.push(v);
                is[v] = true;
            }
        }
    }
    return dep[s] == INF;
}

struct cmp
{
    bool operator () (int a, int b) const
    {
        return dep[a] < dep[b];
    }
};

priority_queue<int, vector<int>, cmp> q;
inline void push(int u)
{
    int nowflow = 0;
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int v = e[i];
        if(!w[i] || dep[u] != dep[v] + 1) continue;
        nowflow = min(flow[u], w[i]);
        w[i] -= nowflow;
        w[i ^ 1] += nowflow;
        flow[u] -= nowflow;
        flow[v] += nowflow;
        if(!is_in[v] && v != t && v != s)
        {
            q.push(v);
            is_in[v] = true;
        }
        if(!flow[u]) break;
    }
}

inline void relabel(int u)
{
    dep[u] = INF;
    for(int i = h[u]; i != -1; i = ne[i])
    {
        if(!w[i]) continue;
        int v = e[i];
        dep[u] = min(dep[u], dep[v] + 1);
    }
}

int maxflow()
{
    if(bfs()) return 0;
    dep[s] = n;
    
    for(int i = 1; i <= n; i ++ )
        if(dep[i] < INF)
            gap[dep[i]] ++;
    
    for(int i = h[s]; i != -1; i = ne[i])
    {
        int v = e[i];
        int nowflow = w[i];
        if(nowflow)
        {
            flow[s] -= nowflow;
            flow[v] += nowflow;
            w[i] -= nowflow;
            w[i ^ 1] += nowflow;
            if(v != t && v != s && !is_in[v])
            {
                q.push(v);
                is_in[v] = true;
            }
        }
    }

    while(q.size())
    {
        int u = q.top();
        q.pop();
        is_in[u] = false;
        push(u);
        if(flow[u])
        {
            gap[dep[u]] --;
            if(!gap[dep[u]])
            {
                for(int i = 1; i <= n; i ++ )
                    if(i != s && i != t && dep[i] > dep[u] && dep[i] < n + 1)
                        dep[i] = n + 1;
            }
            relabel(u);
            gap[dep[u]] ++;
            q.push(u);
            is_in[u] = true;
        }
    }
    return flow[t];
}

补充：二分图

最大匹配：在二分图中选出一些边，使得这些边没有公共顶点，且边的数量最大。

最小点覆盖：选最少的点，满足每条边至少有一个端点被选。

最大独立集：选最多的点，满足两两点之间没有边直接相连。

最小路径覆盖：DAG 中用最少的不相交的路径将所有点连接。

König 定理

在二分图中，最大匹配=最小点覆盖=总点数-最大独立集=总点数-最小路径覆盖

最小割

定义

割：点的划分方式，将点集划分为 SS 和 T=V−ST = V - S 两个集合，使得 s∈Ss \in S 且 t∈Tt \in T。

割的容量：所有从 SS 到 TT 的边的容量之和，记为 c(S,T)c(S, T) 或 c(s,t)c(s, t)

最大流最小割定理

f(s,t)max=c(s,t)minf(s, t)_{max} = c(s, t)_min

应用

普通网络流

边的流量可以用来建模成对某个条件使用的限制次数，建出图跑最大流。

二分图最大匹配

对于一张二分图，我们可以建一个超级源点 ss 和超级汇点 tt，ss 向左部点连流量为 11 的边，右部点向 tt 连流量为 11 的边，左部点和右部点直接连流量为 11 的边。从 ss 开始跑最大流即可。

二分图多重匹配

对于每一个点，它的最大匹配数对应的就是超级源点/汇点和它之间边的最大流量大小。建图跑最大流即可。

例题

P2065 [TJOI2011] 卡片

本题组数就可看成匹配的对数，两种颜色的卡牌可以看成左部点和右部点，于是建图跑网络流。

发现如果暴力建图是 O(Tn2log⁡n)≈67474250O(Tn^2\log n) \approx 67474250 的，考虑优化。

我们可以将每个点连到它的质因子上，质因子就可以充当一个桥梁，连接具有公因子的点。然后就可以愉快跑最大流了 φ(゜▽゜*)♪

但是这时我们发现好像直接分解质因数的复杂度是 O(TnMAXN)≈316227766O(Tn\sqrt MAXN) \approx 316227766，甚至比之前还慢，我们再考虑考虑怎么优化。

我们可以预处理出所有的质数，然后分解的时候直接用质数去筛即可。

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 1e6 + 10, INF = 0x3f3f3f3f;
int h[N], e[N], ne[N], w[N], idx;
int d[N], now[N];
int primes[N * 10], cnt;
map<int, int> mp;
bool st[N * 10];
int n, m, s, t;
int flow, maxflow;

inline void init(int n)
{
    for(int i = 2; i <= n; i ++ )
    {
        if(!st[i])
        {
            primes[++ cnt] = i;
            mp[i] = cnt;
        }
        for(int j = 1; primes[j] <= n / i; j ++ )
        {
            st[primes[j] * i] = true;
            if(i % primes[j] == 0) break;
        }
    }
}

inline void build(int id, int x, int op)
{
    for(int i = 1; primes[i] <= x / primes[i]; i ++ )
    {
        if(x % primes[i] == 0)
        {
            if(op == 0) add(id, i + m + n + 1, 1);
            else add(i + m + n + 1, id, 1);
            while(x % primes[i] == 0) x /= primes[i]; 
        }
    }
    if(x > 1) 
    {
        if(op == 0) add(id, mp[x] + m + n + 1, 1);
        else add(mp[x] + n + m + 1, id, 1);
    }
}

int main()
{
    int T = read();
    init(10000000);
    while(T -- )
    {
        init();
        n = read(), m = read();
        for(int i = 1; i <= n; i ++ )
        {
            int x = read();
            build(i, x, 0);
        }

        for(int i = 1; i <= m; i ++ )
        {
            int x = read();
            build(i + n, x, 1);
        }

        s = 0, t = N - 2;
        for(int i = 1; i <= n; i ++ ) add(s, i, 1);
        for(int i = 1; i <= m; i ++ ) add(i + n, t, 1);

        while(bfs())
            while(flow = dinic(s, INF))
                maxflow += flow;
        
        cout << maxflow << endl;
        maxflow = 0;
    }
    
    return 0;
}

P2763 试题库问题

本题是一个比较裸的二分图多重匹配，每个试题只能被选一次，每种类别要选 kik_i 次。我们就可以把试题看成右部点，向 TT 连流量为 11 的边，把类型看成左部点，从 SS 向其连流量为 kik_i 的边。

过水我就不放代码了。

P2472 [SCOI2007] 蜥蜴

本题有柱子跳跃次数的限制，我们可以把一根柱子拆成两个点，一个入点一个出点，入点向出点连流量为该柱子所能跳跃的次数的边。从源点向蜥蜴在的位置连流量为 11 的边，跑最大流即可。

注意题中的距离为欧几里得距离。

部分代码：

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
35
36
37
38
39
40
41
42
43
44
for(int i = 1; i <= r; i ++ )
    for(int j = 1; j <= c; j ++ )
    {
        in[get(i, j)] = get(i, j);
        out[get(i, j)] = get2(i, j);
        if(mp[i][j] != '0') add(get(i, j), out[get(i, j)], mp[i][j] - '0');
    }

for(int i = 1; i <= r; i ++ )
    for(int j = 1; j <= c; j ++ )
        if(mp[i][j] != '0')
        {
            k ++;
            x[k] = i, y[k] = j;
        }

for(int i = 1; i <= k; i ++ )
    for(int j = 1; j <= k; j ++ )
    {
        if(i == j) continue;
        if(dist(x[i], y[i], x[j], y[j]) <= maxd * maxd)
            add(out[get(x[i], y[i])], in[get(x[j], y[j])], INF);
    }

for(int i = 1; i <= k; i ++ )
{
    int x1 = x[i], y1 = y[i];
    if(x1 + maxd > r || x1 - maxd < 1 || y1 + maxd > c || y1 - maxd < 1) 
        add(out[get(x[i], y[i])], t, INF);
}

for(int i = 1; i <= r; i ++ )
    for(int j = 1; j <= c; j ++ )
        if(frog[i][j] == 'L')
        {
            add(s, in[get(i, j)], 1);
            num ++;
        }

while(bfs())
    while(flow = dinic(s, INF))
        maxflow += flow;

cout << num - maxflow << endl;

未完待续