【图论】网络流

更新于 分类于 ， 阅读次数： 本文字数： 9.5k 阅读时长 ≈ 9 分钟

网络流问题，包括最大流最小割、费用流

学网络流可以去写著名的网络流24题（搜索引擎随便搜就能有整理和题解），反正我没写完，网络流建模方法非常抽象（？）和有意思。

定义和记法

  • 容量网络：有向图，图的边$ (u, v)$ 有非负的权c(u,v)c(u, v)，称容量，图中有一个被称为源的节点和一个被称为汇的节点。

  • 实际通过每条边的流量记为$ f(u, v)，∗∗残量网络∗∗是一个结构和容量网络相同的有向图，边的权值为，**残量网络**是一个结构和容量网络相同的有向图，边的权值为c(u, v) − f(u, v)$。

  • 所有边上的流量集合被称为网络流。

  • 在容量网络中，可行流满足：

    • 0≤f(u,v)≤c(u,v)0\leq f(u, v)\leq c(u, v)
    • 非源汇点，总出量=总入量
    • f(u,v)=−f(v,u)f(u, v) = −f(v, u)

  • 割：划分成SS 和TT 两个点集使得源点在SS ，汇点在TT 。

  • 割的容量：SS 到TT 所有边的流量之和。求过最大流后的最小割在残余网络中一定出满流，入零流。

最大流/最小割

  • 最大流量

  • 分为两类，增广路和预流推进

  • 增广路即找残差网络上能够从源点到汇点的路，建反图储存每一次增广路最大流，便于反悔

  • 最小割的点集找法：跑完最大流在残差网络从源点走残量大于00 的边，都是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
    bool vst[N], no[N];
    int st[N], top;
    bool dfs(int u, int from, bool flag)
    {
        vst[u] = true;
        st[top++] = u;
        for (int i = head[u]; ~i; i = edge[i].nxt)
        {
            int v = edge[i].to;
            if (edge[i].cap <= edge[i].flow || v == from)
                continue;
            if (!vst[v])
            {
                if (dfs(v, u, edge[i ^ 1].flow < edge[i ^ 1].cap))
                    return true;
            }
            else if (!no[v])
                return true;
        }
        if (!flag)
        {
            while (1)
            {
                int v = st[--top];
                no[v] = true;
                if (v == u)
                    break;
            }
        }
        return false;
    }
    // 跑完最大流后调用
    memset(vis, false, sizeof(vis));
    memset(no, false, sizeof(no));
    top = 0;
    bool flag = dfs(end, end, 0);

Ford-Folkerson

复杂度跟流量有关，一般不用

建图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
struct Edge
{
    int to, nxt;
    ll cap, flow; //
} edge[M];
int tot, head[N];
void init()
{
    tot = 2;
    memset(head, -1, sizeof(head));
}
void add_edge(int u, int v, int w, int rw = 0)
{
    edge[tot].to = v;
    edge[tot].cap = w;
    edge[tot].flow = 0;
    edge[tot].nxt = head[u];
    head[u] = tot++;
    edge[tot].to = u;
    edge[tot].cap = rw; //反图
    edge[tot].flow = 0;
    edge[tot].nxt = head[v];
    head[v] = tot++;
}

暴力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
bool vst[N];
ll dfs(int u, ll flow) //流入u的流量为flow
{
    if (u == t) //到汇点，返回增广答案
        return flow;
    vst[u] = true; //标记访问
    for (int i = head[u]; ~i; i = edge[i].nxt)
    {
        int v = edge[i].to;
        if (vst[v] || edge[i].flow >= edge[i].cap) //如果访问过了或者这条路没有流量了
            continue;
        int res = dfs(v, min(edge[i].cap - edge[i].flow, flow)); //dfs找，更新路上最小流量
        if (res > 0) //记录这条增广路
        {
            edge[i].flow += res; //该路流量增加
            edge[i ^ 1].flow -= res; //反图流量减少
            return res;
        }
    }
    return 0;
}
ll FF(int s, int t, int n)
{
    ll res = 0, ans = 0;
    while (1)
    {
        memset(vst, 0, sizeof(vst));
        res = dfs(s, INF); //dfs找增广路
        if (res <= 0)      //找不到增广路了
            break;
        ans += res;
    }
    return ans;
}

Edmonds-Karp

BFS找增广路，每碰到汇点就增广，复杂度O(nm2)O(nm^2) ，一般不用。

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
struct Edge
{
    int from, to, cap, flow;
    Edge(int u, int v, int c, int f) : from(u), to(v), cap(c), flow(f) {}
};
struct EK
{
    int n, m;           // n：点数，m：边数
    vector<Edge> edges; // edges：所有边的集合
    vector<int> G[N];   // G：点 x -> x 的所有边在 edges 中的下标
    ll a[N];            // a：点 x -> BFS 过程中最近接近点 x 的边给它的最大流
    int p[N];           // p：点 x -> BFS 过程中最近接近点 x 的边
    void init(int n)
    {
        for (int i = 0; i < n; i++)
            G[i].clear();
        edges.clear();
    }
    void add_edge(int from, int to, int cap)
    {
        edges.push_back(Edge(from, to, cap, 0));
        edges.push_back(Edge(to, from, 0, 0)); //反向边
        m = edges.size();
        G[from].push_back(m - 2);
        G[to].push_back(m - 1);
    }
    ll Maxflow(int s, int t)
    {
        ll flow = 0;
        while (1)
        {
            memset(a, 0, sizeof(a));
            queue<int> Q;
            Q.push(s);
            a[s] = INF;
            while (!Q.empty())
            {
                int x = Q.front();
                Q.pop();
                for (int i = 0; i < G[x].size(); i++)
                { // 遍历以 x 作为起点的边
                    Edge &e = edges[G[x][i]];
                    if (!a[e.to] && e.cap > e.flow)
                    {
                        p[e.to] = G[x][i];                   // G[x][i]是最近接近点e.to的边
                        a[e.to] = min(a[x], e.cap - e.flow); // 最近接近点e.to的边赋给它的流
                        Q.push(e.to);
                    }
                }
                if (a[t])
                    break; // 如果汇点接受到了流，就退出 BFS
            }
            if (!a[t])
                break; // 如果汇点没有接受到流，说明源点和汇点不在同一个连通分量上
            for (int u = t; u != s; u = edges[p[u]].from)
            {                                 // 通过 u 追寻 BFS 过程中 s -> t 的路径
                edges[p[u]].flow += a[t];     // 增加路径上边的 flow 值
                edges[p[u] ^ 1].flow -= a[t]; // 减小反向路径的 flow 值
            }
            flow += a[t];
        }
        return flow;
    }
} ek;

Dinic

  • 每次都走最短的增广路，允许多条增广路一起增广。
  • BFS分层，形成层次网络
  • 每次只走level[u]=level[v]−1level[u]=level[v]-1的路，确保找到最短的增广路，且每条边只走一次，即一个可走弧优化和只走一次的剪枝
  • bfs能走的时候，不断dfs增广路
  • 最坏复杂度O(nm2)O(nm^2)
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
int dep[N], Q[N];
int qhead, qtail;
bool bfs() // bfs残量网络，返回是否搜到了汇点
{
    memset(dep, -1, (n + 1) * sizeof(int));
    qhead = qtail = 0;
    Q[qtail++] = s;
    dep[s] = 0;
    while (qhead < qtail)
    {
        int u = Q[qhead++];
        for (int i = head[u]; ~i; i = edge[i].nxt)
        {
            int v = edge[i].to;
            if (edge[i].flow >= edge[i].cap || ~dep[v])
                continue;
            dep[v] = dep[u] + 1;
            Q[qtail++] = v;
        }
    }
    return ~dep[t]; //dep[t] != -1，就是搜到了汇点
}
ll dfs(int u, ll flow)
{
    if (u == t)
        return flow;
    ll tp = 0; //本轮增广的总流量
    for (int i = head[u]; ~i; i = edge[i].nxt)
    {
        int v = edge[i].to;
        if (edge[i].flow < edge[i].cap && dep[v] == dep[u] + 1) // 允许走的弧
        {
            ll res = dfs(v, min(edge[i].cap - edge[i].flow, flow)); //本次增广的最大流
            edge[i].flow += res;
            edge[i ^ 1].flow -= res;
            flow -= res; //流量限制更新
            tp += res;   //增广的总流量增加
        }
    }
    if (tp == 0)     // 走不到汇点
        dep[u] = -1; // 剪枝，本轮增广不用走这里了
    return tp;
}
ll Dinic()
{
    ll ans = 0;
    while (bfs())
        ans += dfs(s, LINF);
    return ans;
}

kuangbin的板子：

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
int Q[N];
int dep[N], cur[N], sta[N];
bool bfs()
{
    int qhead = 0, qtail = 0;
    memset(dep, -1, sizeof(dep[0]) * (n + 1));
    dep[s] = 0;
    Q[qtail++] = s;
    while (qhead < qtail)
    {
        int u = Q[qhead++];
        for (int i = head[u]; ~i; i = edge[i].nxt)
        {
            int v = edge[i].to;
            if (edge[i].cap > edge[i].flow && dep[v] == -1)
            {
                dep[v] = dep[u] + 1;
                if (v == t)
                    return true;
                Q[qtail++] = v;
            }
        }
    }
    return false;
}
ll dinic()
{
    ll maxflow = 0;
    while (bfs())
    {
        for (int i = 1; i <= n; i++)
            cur[i] = head[i];
        int u = s, qtail = 0;
        while (~cur[s])
        {
            if (u == t) //找到一条增广路
            {
                ll tp = LINF;
                for (int i = qtail - 1; i >= 0; i--) //更新该增广路上的最大流
                    tp = min(tp, edge[sta[i]].cap - edge[sta[i]].flow);
                maxflow += tp;                       //更新总流量
                for (int i = qtail - 1; i >= 0; i--) //更新该增广路上的信息
                {
                    edge[sta[i]].flow += tp;
                    edge[sta[i] ^ 1].flow -= tp;
                    if (edge[sta[i]].cap - edge[sta[i]].flow == 0)
                        qtail = i; //如果有一条路后面没办法走了就从这里截断
                }
                u = edge[sta[qtail] ^ 1].to; //最前面走不了的那条反路的到达，即正路的起始节点
            }
            else if (~cur[u] && edge[cur[u]].cap > edge[cur[u]].flow && dep[u] + 1 == dep[edge[cur[u]].to])
            {
                sta[qtail++] = cur[u];
                u = edge[cur[u]].to;
            }
            else
            {
                while (u != s && cur[u] == -1)
                    u = edge[sta[--qtail] ^ 1].to;
                cur[u] = edge[cur[u]].nxt;
            }
        }
    }
    return maxflow;
}

ISAP

优化Dinic的反复bfs：每次找到的增广路上节点都将层数+1，直到断层或源点层数为n

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
int Q[N];
int dep[N], cur[N], gap[N], st[N]; // gap[i]记录层数为i的有多少个节点，st是栈
void bfs()
{
    int qhead = 0, qtail = 0;
    memset(dep, -1, sizeof(dep[0]) * (n + 1));
    gap[0] = 1;
    dep[t] = 0;
    Q[qtail++] = t; //注意是倒着bfs
    while (qhead != qtail)
    {
        int u = Q[qhead++];
        for (int i = head[u]; ~i; i = edge[i].nxt)
        {
            int v = edge[i].to;
            if (~dep[v])
                continue;
            Q[qtail++] = v;
            dep[v] = dep[u] + 1;
            gap[dep[v]]++;
        }
    }
}
ll sap()
{
    bfs();
    memcpy(cur, head, sizeof(head));
    int top = 0;
    int u = s;
    ll ans = 0;
    while (dep[s] < n)
    {
        if (u == t) // 找到一条增广路
        {
            ll Min = LINF;
            int pos = 0;
            for (int i = 0; i < top; i++)
                if (Min > edge[st[i]].cap - edge[st[i]].flow)
                { // 找到该增广路的最大流
                    Min = edge[st[i]].cap - edge[st[i]].flow;
                    pos = i;
                }
            for (int i = 0; i < top; i++) //更新路径上的流量信息
            { 
                edge[st[i]].flow += Min;
                edge[st[i] ^ 1].flow -= Min;
            }
            ans += Min;
            top = pos;
            u = edge[st[top] ^ 1].to;
            continue;
        }
        bool flag = false; // 标记是否能继续找增广路了
        for (int i = cur[u]; ~i; i = edge[i].nxt)
        {
            int v = edge[i].to;
            if (edge[i].cap - edge[i].flow && dep[v] + 1 == dep[u]) 
            { // dfs的迭代写法，找u出去可以拓展的增广路
                flag = true;
                cur[u] = i;
                st[top++] = i;
                u = v;
                break;
            }
        }
        if (flag)
            continue;
        int Min = n; // dfs完了所有边
        for (int i = head[u]; ~i; i = edge[i].nxt)
            if (edge[i].cap - edge[i].flow && dep[edge[i].to] < Min)
            { //找残余网络中有剩余流量且层数最小的相邻节点
                Min = dep[edge[i].to];
                cur[u] = i;
            }
        gap[dep[u]]--; // 当前节点层数更新前先更新该层节点数
        if (!gap[dep[u]]) // 断层了，必然找不到增广路了，退出
            return ans;
        dep[u] = Min + 1; // 当前节点层数+1
        gap[dep[u]]++;
        if (u != s)
            u = edge[st[--top] ^ 1].to;
    }
    return ans;
}

对偶图

  • 平面图中边分开的每个区域设成一个节点，每条边左右的区域连边，左右是同一区域连的就是自环，得到原图的对偶图
  • 对偶图上求解最短路=最大流=最小割

技巧

  • 技巧1：超级源点和超级汇点的建立
  • 技巧2：点有流量限制：拆点成uinu_{in} 和uoutu_{out} ，入边接in，出边从out接，这两点之间连一条点流量限制的边。
  • 技巧3：容量的含义可以想到“限制”有关的题

费用流

最小/大费用最大流：每条路有收费

这里给出最小费用算法，最大费用将费用取相反数，结果再取相反数

SPFA

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
//建图：Edge多一个cost变量，建图时正边赋cost，反边赋-cost，其他不变
ll dis[N];
bool vst[N];
int pre[N];
bool spfa(int s, int t)
{
    queue<int> q;
    for (int i = 1; i <= n; i++)
    {
        dis[i] = INF;
        vst[i] = false;
        pre[i] = -1;
    }
    dis[s] = 0;
    vst[s] = true;
    q.push(s);
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        vst[u] = false;
        for (int i = head[u]; ~i; i = edge[i].nxt)
        {
            int v = edge[i].to;
            if (edge[i].cap > edge[i].flow && dis[v] > dis[u] + edge[i].cost)
            {
                dis[v] = dis[u] + edge[i].cost;
                pre[v] = i;
                if (!vst[v])
                {
                    vst[v] = true;
                    q.push(v);
                }
            }
        }
    }
    if (pre[t] == -1)
        return false;
    else
        return true;
}
ll cost,flow;
ll minCostMaxflow() //返回最大流，cost是最小费用
{
    ll maxflow = 0;
    cost = 0;
    while (spfa(s, t))
    {
        ll tp = LINF;
        for (int i = pre[t]; ~i; i = pre[edge[i ^ 1].to])
        {
            if (tp > edge[i].cap - edge[i].flow)
                tp = edge[i].cap - edge[i].flow;
        }
        for (int i = pre[t]; ~i; i = pre[edge[i ^ 1].to])
        {
            edge[i].flow += tp;
            edge[i ^ 1].flow -= tp;
            cost += edge[i].cost * tp;
        }
        maxflow += tp;
    }
    return maxflow;
}

最小费用可行流

  • 考虑一张网络流图，每条边定义为(u,v,w,l,r)(u,v,w,l,r)，代表从uu 到vv 的一条有向边，费用为ww ，容量为[l,r][l,r] 闭区间，源点ss 汇点tt 已知，且保证源点没有入边、汇点没有出边，同时定义常规费用流图的边为(u,v,w,cap)(u,v,w,cap)

  • 现在我们需要求这张图的最小费用可行流（就是满足所有边的流量上下限制，同时费用最小）

  • 按照如下方式建立附加边和附加点：

    • 建立附加源点SSSS ，和附加汇点TTTT

    • 对于原图中每一个点（包括源汇）uu ，令d[u]d[u] 代表uu 点的所有入边的流量下界减去出边的流量下界

      • 如果d[u]d[u] 是负数，那么从uu 连一条边(u,TT,0,−d[u])(u,TT,0,-d[u]) 到TTTT
      • 如果d[u]d[u] 是正数，那么从SSSS 连一条边(SS,u,0,d[u])(SS,u,0,d[u]) 到uu

    • 对于原图中每一条边(u,v,w,l,r)(u,v,w,l,r) ，连边(u,v,w,r−l)(u,v,w,r-l)

  • 连边(t,s,0,inf)(t,s,0,inf) （注意这里是原图的源汇点！不是附加的源汇点！！）

  • 这样以后，从SSSS 到$ TT$ 跑新图的最小费用最大流，再加上原图中每条边的下界流量乘以费用（必须跑的部分），就是最小费用可行流的费用了s