yaoxi-std 的博客

$\text{开}\mathop{\text{卷}}\limits^{ju\check{a}n}\text{有益}$

0%

【专题】网络流

发表于 更新于 分类于

【专题】网络流

网络流的话，先口糊好怎么建图，然后复制默写一下板子就好了。

难点其实有两个，一个是如何建图，另一个是输出路径。

如果一道题有许多奇怪的限制，并且$n$和$m$很小，导致$O(n^2m)$可以通过，就可以往网络流方面去想。

其实网络流24题的全称叫网络流和线性规划24题？

费用流需要注意的地方

  1. 费用流建反边的$cost$是原来的$cost$的相反数，即需要add(u, v, c, f), add(v, u, -c, 0);
  2. 计算流量的方式和普通网络流相同，但是计算总$cost$是每次加上edge.cost * flow，不要忘记乘上$cost$，用全局变量存$cost$会好写一些。
  3. 由于费用流的边权可能$\le 0$，所以必须用$spfa$而无法使用$dijkstra$，并且$dfs$增广时必须开$vis$数组防止无限递归。
  4. （这应该算是个小$tip$）网络流$tot$一开始清空成$1$可以不需要再调用init函数，也不需要再把$head$清空成$-1$。

流模型

P2756 飞行员配对方案问题
P4016 负载平衡问题
P1251 餐巾计划问题
P2754 星际转移问题
P2763 试题库问题
P2764 最小路径覆盖问题
P2765 魔术球问题
P2766 最长不下降子序列问题
P2770 航空路线问题
P3254 圆桌问题
P3356 火星探险问题
P3357 最长k可重线段集问题
P3358 最长k可重区间集问题
P4012 深海机器人问题
P4013 数字梯形问题
P4014 分配问题
P4015 运输问题

割模型

P2762 太空飞行计划问题
P2774 方格取数问题
P3355 骑士共存问题

非模型

P276 软件补丁问题
P4011 孤岛营救问题
P4009 汽车加油行驶问题

模版代码

网络流(dinic)

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
struct Dinic {
    struct Edge {
        int v, flow;
    } edge[MAXM * 2];
    int tot = 1, flow = 0;
    int head[MAXN], nxt[MAXM * 2], lev[MAXN], cur[MAXN];
    void addedge(int u, int v, int flow) {
        edge[++tot] = {v, flow};
        nxt[tot] = head[u], head[u] = tot;
        edge[++tot] = {u, 0};
        nxt[tot] = head[v], head[v] = tot;
    }
    bool bfs(int s, int t) {
        fill(lev, lev + MAXN, -1);
        queue<int> que;
        que.push(s);
        lev[s] = 0;
        while (!que.empty()) {
            int u = que.front();
            que.pop();
            for (int i = head[u]; i; i = nxt[i]) {
                int v = edge[i].v;
                if (edge[i].flow && lev[v] == -1) {
                    lev[v] = lev[u] + 1;
                    que.push(v);
                }
            }
        }
        return lev[t] != -1;
    }
    int augment(int u, int t, int mx) {
        if (u == t || mx == 0)
            return mx;
        int ret = 0;
        for (int &i = cur[u]; i; i = nxt[i]) {
            int v = edge[i].v;
            if (lev[v] != lev[u] + 1)
                continue;
            int tmp = augment(v, t, min(mx, edge[i].flow));
            mx -= tmp, ret += tmp;
            edge[i].flow -= tmp, edge[i ^ 1].flow += tmp;
            if (mx == 0)
                break;
        }
        return ret;
    }
    int maxflow(int s, int t) {
        while (bfs(s, t)) {
            copy(head, head + MAXN, cur);
            flow += augment(s, t, INF);
        }
        return flow;
    }
} network;

网络流 (HLPP)

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
struct HLPP {
    struct Edge {
        int v; ll flow;
    } edge[MAXE * 2];
    int n, s, t, tot = 1;
    int head[MAXV], nxt[MAXE * 2];
    int h[MAXV], gap[MAXV * 2], inq[MAXV];
    ll e[MAXV];
    priority_queue<pair<int, int>> pq;
    inline void init(int n) { this->n = n; }
    inline void addedge(int u, int v, ll f) {
        edge[++tot] = {v, f}, nxt[tot] = head[u], head[u] = tot;
        edge[++tot] = {u, 0}, nxt[tot] = head[v], head[v] = tot;
    }
    inline bool bfs() {
        int fr = 0, bk = 0;
        static int que[MAXN];
        fill(h + 1, h + n + 1, INF);
        h[t] = 0, que[++bk] = t;
        while (fr < bk) {
            int u = que[++fr];
            for (int i = head[u]; i; i = nxt[i])
                if (h[edge[i].v] > h[u] + 1 && edge[i ^ 1].flow)
                    h[edge[i].v] = h[u] + 1, que[++bk] = edge[i].v;
        }
        return h[s] != INF;
    }
    inline void push(int u) {
        for (int i = head[u]; i; i = nxt[i])
            if (h[edge[i].v] + 1 == h[u] && edge[i].flow) {
                ll tmp = min(edge[i].flow, e[u]);
                edge[i].flow -= tmp, edge[i ^ 1].flow += tmp;
                e[u] -= tmp, e[edge[i].v] += tmp;
                if (edge[i].v != s && edge[i].v != t && !inq[edge[i].v])
                    pq.push({h[edge[i].v], edge[i].v}), inq[edge[i].v] = 1;
                if (!e[u]) break;
            }
    }
    inline void relabel(int u) {
        h[u] = INF;
        for (int i = head[u]; i; i = nxt[i])
            if (h[u] > h[edge[i].v] + 1 && edge[i].flow)
                h[u] = h[edge[i].v] + 1;
    }
    inline ll maxflow(int s, int t) {
        this->s = s, this->t = t;
        if (!bfs()) return e[t];
        h[s] = n;
        for (int i = 1; i <= n; ++i)
            if (h[i] < INF) ++gap[h[i]];
        for (int i = head[s]; i; i = nxt[i])
            if (ll d = edge[i].flow) {
                edge[i].flow -= d, edge[i ^ 1].flow += d;
                e[s] -= d, e[edge[i].v] += d;
                if (edge[i].v != s && edge[i].v != t && !inq[edge[i].v])
                    pq.push({h[edge[i].v], edge[i].v}), inq[edge[i].v] = 1;
            }
        while (pq.size()) {
            int u = pq.top().second; pq.pop();
            inq[u] = 0, push(u);
            if (e[u]) {
                if (h[u] != INF && !--gap[h[u]]) {
                    for (int i = 1; i <= n; ++i)
                        if (i != s && i != t && h[u] < h[i] && h[i] < n + 1)
                            h[i] = n + 1;
                }
                relabel(u), ++gap[h[u]], pq.push({h[u], u});
            }
        }
        return e[t];
    }
} network;

最小费用最大流(dinic)

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
template <const int MAXV, const int MAXE>
struct MCMF {
    const int INF = 0x3f3f3f3f3f3f3f3f;
    struct Edge {
        int v, flow, cost;
    } edge[MAXE * 2];
    int tot = 1, head[MAXV], nxt[MAXE];
    int flow, cost, cur[MAXV], dis[MAXV];
    bool vis[MAXV];
    void addedge(int u, int v, int flow, int cost) {
        edge[++tot] = {v, flow, cost};
        nxt[tot] = head[u], head[u] = tot;
        edge[++tot] = {u, 0, -cost};
        nxt[tot] = head[v], head[v] = tot;
    }
    bool spfa(int s, int t) {
        fill(vis, vis + MAXV, 0);
        fill(dis, dis + MAXV, INF);
        queue<int> que;
        que.push(s);
        dis[s] = 0;
        vis[s] = 1;
        while (!que.empty()) {
            int u = que.front();
            que.pop();
            vis[u] = 0;
            for (int i = head[u]; i; i = nxt[i]) {
                int v = edge[i].v;
                if (edge[i].flow && dis[v] > dis[u] + edge[i].cost) {
                    dis[v] = dis[u] + edge[i].cost;
                    if (!vis[v]) {
                        que.push(v);
                        vis[v] = 1;
                    }
                }
            }
        }
        return dis[t] != INF;
    }
    int augment(int u, int t, int mx) {
        if (u == t || mx == 0)
            return mx;
        vis[u] = 1;
        int ret = 0;
        for (int &i = cur[u]; i; i = nxt[i]) {
            int v = edge[i].v;
            if (vis[v] || dis[v] != dis[u] + edge[i].cost)
                continue;
            int tmp = augment(v, t, min(mx, edge[i].flow));
            cost += tmp * edge[i].cost;
            mx -= tmp, ret += tmp;
            edge[i].flow -= tmp, edge[i ^ 1].flow += tmp;
            if (mx == 0)
                break;
        }
        vis[u] = 0;
        return ret;
    }
    pair<int, int> mcmf(int s, int t) {
        while (spfa(s, t)) {
            copy(head, head + MAXV, cur);
            flow += augment(s, t, INF);
        }
        return make_pair(flow, cost);
    }
};