网络流 24 题 | guanghechen

Prepare
¶

由于网络流问题难点在于建模，网络流算法基本都是围绕增广路，且相关的文章网上已经有许多了，故此下文中将给出会多次使用到的模板代码，而且其具体的算法略去。

ISAP

isap.hpp | 107 lines.

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
#include <cstring>
#include <queue>
#include <vector>

namespace ISAP {
  static const int MAXN = 10000 + 10;
  static const int INF = 0x3f3f3f3f;

  struct Edge {
    int from, to, cap, flow;
    Edge(int from = 0, int to = 0, int cap = 0, int flow = 0)
        : from(from), to(to), cap(cap), flow(flow) {
    }
  };

  int s, t, n;
  int cnt[MAXN];
  int cur[MAXN];
  int path[MAXN];
  int dist[MAXN];
  std::vector<Edge> edges;
  std::vector<int> G[MAXN];
  std::queue<int> Q;

  void addedge(int from, int to, int cap) {
    int siz = edges.size();
    edges.push_back(Edge(from, to, cap, 0));
    edges.push_back(Edge(to, from, 0, 0));
    G[from].push_back(siz);
    G[to].push_back(siz + 1);
  }

  void BFS() {
    memset(dist, -1, sizeof dist);

    Q.push(t);
    dist[t] = 0;

    while (!Q.empty()) {
      int o = Q.front();
      Q.pop();
      for (int i = 0; i < G[o].size(); ++i) {
        Edge& e = edges[G[o][i]];
        if (dist[e.to] == -1 && e.cap == 0) {
          dist[e.to] = dist[o] + 1;
          Q.push(e.to);
        }
      }
    }
  }

  int augment() {
    int mif = INF;
    for (int o = t; o != s;) {
      Edge& e = edges[path[o]];
      mif = std::min(mif, e.cap - e.flow);
      o = e.from;
    }
    for (int o = t; o != s;) {
      edges[path[o]].flow += mif;
      edges[path[o] ^ 1].flow -= mif;
      o = edges[path[o]].from;
    }
    return mif;
  }

  int maxflow() {
    BFS();
    memset(cur, 0, sizeof cur);
    memset(cnt, 0, sizeof cnt);
    for (int i = 0; i < n; ++i)
      if (dist[i] < n) ++cnt[dist[i]];

    int ans = 0;
    for (int o = s; dist[o] < n;) {
      if (o == t) ans += augment(), o = s;
      bool ok = false;
      for (int i = cur[o]; i < G[o].size(); ++i) {
        Edge& e = edges[G[o][i]];
        if (e.cap > e.flow && dist[o] == dist[e.to] + 1) {
          ok = true;
          cur[o] = i;
          path[e.to] = G[o][i];
          o = e.to;
          break;
        }
      }
      if (!ok) {
        int d = n - 1;
        for (int i = 0; i < G[o].size(); ++i) {
          Edge& e = edges[G[o][i]];
          if (e.cap > e.flow) d = std::min(d, dist[e.to]);
        }
        if (--cnt[dist[o]] == 0) break;
        ++cnt[dist[o] = d + 1];
        cur[o] = 0;
        if (o != s) o = edges[path[o]].from;
      }
    }
    return ans;
  }

  void solve();
  void solve(int);
  void solve(int, int);
  void solve(int, int, int);
};   // namespace ISAP

Dinic

dinic.hpp | 83 lines.

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
#include <cstring>
#include <queue>
#include <vector>

namespace Dinic {
  static const int MAXN = 10000 + 10;
  static const int INF = 0x3f3f3f3f;

  struct Edge {
    int from, to, cap, flow;
    Edge(int from = 0, int to = 0, int cap = 0, int flow = 0)
        : from(from), to(to), cap(cap), flow(flow) {
    }
  };

  int s, t;
  int cur[MAXN];
  int dist[MAXN];
  std::queue<int> Q;
  std::vector<Edge> edges;
  std::vector<int> G[MAXN];

  void addedge(int from, int to, int cap) {
    int siz = edges.size();
    edges.push_back(Edge(from, to, cap, 0));
    edges.push_back(Edge(to, from, 0, 0));
    G[from].push_back(siz);
    G[to].push_back(siz + 1);
  }

  bool BFS() {
    memset(dist, -1, sizeof dist);

    Q.push(s);
    dist[s] = 0;

    while (!Q.empty()) {
      int o = Q.front();
      Q.pop();
      for (int i = 0; i < G[o].size(); ++i) {
        Edge& e = edges[G[o][i]];
        if (dist[e.to] == -1 && e.cap > e.flow) {
          dist[e.to] = dist[o] + 1;
          Q.push(e.to);
        }
      }
    }

    return dist[t] != -1;
  }

  int DFS(int o, int minflow) {
    if (o == t || minflow == 0) return minflow;
    int flow = 0;
    for (int& i = cur[o]; i < G[o].size(); ++i) {
      Edge& e = edges[G[o][i]];
      if (dist[e.to] == dist[o] + 1) {
        int f = DFS(e.to, std::min(minflow, e.cap - e.flow));
        if (f <= 0) continue;
        e.flow += f;
        edges[G[o][i] ^ 1].flow -= f;
        flow += f;
        minflow -= f;
        if (minflow == 0) break;
      }
    }
    return flow;
  }

  int maxflow() {
    int ans = 0;
    while (BFS()) {
      memset(cur, 0, sizeof cur);
      ans += DFS(s, INF);
    }
    return ans;
  }

  void solve();
  void solve(int);
  void solve(int, int);
  void solve(int, int, int);
};   // namespace Dinic

费用流：(Min cost Max flow)

mcmf.hpp | 90 lines.

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
#include <cstring>
#include <queue>
#include <vector>

namespace MCMF {
  const int MAXN = 10000 + 10;
  const int INF = 0x3f3f3f3f;

  struct Edge {
    int from, to, cap, flow, cost;
    Edge(int from = 0, int to = 0, int cap = 0, int flow = 0, int cost = 0)
        : from(from), to(to), cap(cap), flow(flow), cost(cost) {
    }
  };

  int s, t;
  int cost, flow;
  int path[MAXN];
  int dist[MAXN];
  std::vector<Edge> edges;
  std::vector<int> G[MAXN];

  void init(int source = 0, int converge = 1, int N = MAXN) {
    s = source;
    t = converge;
    cost = 0;
    flow = 0;
    edges.clear();
    for (int i = 0; i < N; ++i) G[i].clear();
  }

  void addedge(int from, int to, int cap, int cost) {
    int siz = edges.size();
    edges.push_back(Edge(from, to, cap, 0, cost));
    edges.push_back(Edge(to, from, 0, 0, -cost));
    G[from].push_back(siz);
    G[to].push_back(siz + 1);
  }

  bool spfa() {
    static std::queue<int> Q;
    static bool inq[MAXN];

    memset(dist, 0x3f, sizeof dist);
    Q.push(s);
    inq[s] = true;
    dist[s] = 0;

    while (!Q.empty()) {
      int o = Q.front();
      Q.pop();
      for (int i = 0; i < G[o].size(); ++i) {
        Edge& e = edges[G[o][i]];
        if (e.cap > e.flow && dist[e.to] > dist[o] + e.cost) {
          dist[e.to] = dist[o] + e.cost;
          path[e.to] = G[o][i];
          if (inq[e.to]) continue;
          inq[e.to] = true;
          Q.push(e.to);
        }
      }
      inq[o] = false;
    }

    return dist[t] != INF;
  }

  std::pair<int, int> mincostmaxflow() {
    while (spfa()) {
      int mif = INF;
      for (int o = t; o != s;) {
        Edge& e = edges[path[o]];
        mif = std::min(mif, e.cap - e.flow);
        o = e.from;
      }
      for (int o = t; o != s;) {
        edges[path[o]].flow += mif;
        edges[path[o] ^ 1].flow -= mif;
        o = edges[path[o]].from;
      }
      flow += mif;
      cost += mif * dist[t];
    }
    return std::make_pair(flow, cost);
  }

  void dfs();

  void solve();
};   // namespace MCMF

I/O read

read.hpp | 11 lines.

1
2
3
4
5
6
7
8
9
10
11
#include <cstdio>

inline int read() {
  bool positive = true;
  char c = getchar();
  int s = 0;
  for (; c < '0' || c > '9'; c = getchar())
    if (c == '-') positive = false;
  for (; c >= '0' && c <= '9'; c = getchar()) s = s * 10 + c - '0';
  return positive ? s : -s;
}

Problems
¶

01 飞行员配对方案问题
¶

题目链接： Power OJ/1736

经典的二分图模型：

外籍飞行员作为左侧点，英国飞行员作为右侧点，可以互相配合的飞行员之间连一条容量为 $1$ 的边
建立源点 $s$ ，并从 $s$ 对左侧的每个点引一条容量为 $1$ 的边
建立汇点 $t$ ，并从右侧的每个点向 $t$ 引一条容量为 $1$ 的边

然后跑最大流。至于方案，仅需考虑满流的边 $⟨ μ, ν ⟩$ （其中 $μ \in$ 左侧的点集， $ν \in$ 右侧的点集），那么 $μ$ 和 $ν$ 是一对搭档。

01.cpp | 55 lines.

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
#include "./isap.hpp"
#include <bits/stdc++.h>

void ISAP::solve(int N, int M) {
  s = 0;
  t = M + 1;
  n = M + 2;
  int ans = maxflow();
  if (ans > 0) {
    printf("%d\n", ans);
    for (int o = 0; o < N; ++o) {
      Edge& e = edges[G[0][o]];
      if (e.cap == e.flow) {
        for (auto& i : G[e.to]) {
          Edge& e2 = edges[i];
          if (e2.cap == e2.flow) {
            printf("%d %d\n", e.to, e2.to);
            break;
          }
        }
      }
    }
  } else
    puts("No Solution!");
}

inline int read() {
  bool positive = true;
  char c = getchar();
  int s = 0;
  for (; c < '0' || c > '9'; c = getchar())
    if (c == '-') positive = false;
  for (; c >= '0' && c <= '9'; c = getchar()) s = s * 10 + c - '0';
  return positive ? s : -s;
}

int main() {
  int N = read();
  int M = read();

  for (int i = 1; i <= N; ++i) ISAP::addedge(0, i, 1);

  for (int i = N + 1; i <= M; ++i) ISAP::addedge(i, M + 1, 1);

  while (true) {
    int u = read();
    int v = read();
    if (u == -1 && v == -1) break;
    if (u > v) std::swap(u, v);
    ISAP::addedge(u, v, 1);
  }

  ISAP::solve(N, M);
  return 0;
}

02 太空飞行计划问题
¶

题目链接： Power OJ/1737

经典的最大权闭合图问题（关于最大权闭合图可以参见网络流基础之最大权闭合图）：

设实验 $i$ 获利为 $x_{i}$ ，实验仪器 $j$ 花费为 $y_{j}$
将每个实验与实验所需仪器连边，且容量设为 $\infty$
建立源点 $s$ ，并从 $s$ 对所有的实验引一条容量为 $α \times x + β$ 的边（其中， $α$ 与 $β$ 的作用及取值在网络流基础之最大权闭合图一文中有详细讨论）
建立汇点 $t$ ，并从所有的实验仪器向 $t$ 引一条容量为 $α \times y$ 的边

然后跑最大流， $(\sum x)$ -最大流量即是答案。
至于方案，仅需考虑满流的边所连接的节点即可。

02.cpp | 79 lines.

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
#include "./isap.hpp"
#include <bits/stdc++.h>

void ISAP::solve(int M, int N, int tot) {
  static bool used[MAXN];
  static std::stack<int> st;
  memset(used, 0, sizeof used);

  s = 0;
  t = M + N + 1;
  n = M + N + 2;
  int ans = tot - maxflow();

  st.push(s);
  while (!st.empty()) {
    int o = st.top();
    st.pop();
    used[o] = true;
    for (auto& i : G[o]) {
      Edge& e = edges[i];
      if (e.cap > e.flow && !used[e.to]) st.push(e.to);
    }
  }

  for (int i = 1; i <= M; ++i)
    if (used[i]) printf("%d ", i);
  putchar('\n');
  for (int i = 1; i <= N; ++i)
    if (used[M + i]) printf("%d ", i);
  putchar('\n');
  printf("%d\n", ans >> 16);
}

inline int read() {
  bool positive = true;
  char c = getchar();
  int s = 0;
  for (; c < '0' || c > '9'; c = getchar())
    if (c == '-') positive = false;
  for (; c >= '0' && c <= '9'; c = getchar()) s = s * 10 + c - '0';
  return positive ? s : -s;
}

const int INF = 0x3f3f3f3f;
const int partail = (1 << 16) - 1;

char s[10000], *ss;
inline int nextint(char*& s) {
  for (; *s < '0' || *s > '9'; s++)
    if (*s == '\n') return -1;
  int num = 0;
  for (; *s >= '0' && *s <= '9'; s++) num = num * 10 + *s - '0';
  return num;
}

int main() {
  int M = read();
  int N = read();
  int tot = 0;

  for (int i = 1; i <= M; ++i) {
    for (ss = s; (*ss = getchar()) == '\n';)
      ;
    for (ss = s + 1; (*ss = getchar()) != '\n'; ++ss)
      ;
    ss = s;
    int val = nextint(ss) << 16 | 1;
    ISAP::addedge(0, i, val);
    for (int id; (id = nextint(ss)) != -1;) ISAP::addedge(i, M + id, INF);
    tot += val;
  }
  for (int i = 1; i <= N; ++i) {
    int val = read() << 16;
    ISAP::addedge(M + i, M + N + 1, val);
  }

  ISAP::solve(M, N, tot);
  return 0;
}

03 最小路径覆盖问题
¶

题目链接： Power OJ/1738

经典的有向无环图最小路径覆盖问题：

最小路径覆盖要求的是有向无环图，将原图每个点拆成两个，显然新图是一个二分图
求出二分图最大匹配，最小路径覆盖数=原图点数-新图最大匹配数。

简单证明：初始时可以看做有 $N$ 个长度为 0 的路径，每得到一个匹配相当于合并两条路径。
至于方案，从左侧任意一个未访问过的点出发，经沿着交替路走，得到的就是最小路径覆盖中的一条路径。

考虑到使用网络流求出路径比较麻烦 = =，仅给出二分图的 增广路算法 的实现。

03.cpp | 83 lines.

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
#include <bits/stdc++.h>

const int MAXN = 1000 + 10;
const int INF = 0x3f3f3f3f;

namespace hungary {
  int L, R;
  std::vector<int> G[MAXN];
  int left[MAXN], right[MAXN];
  bool mark[MAXN];

  void init(int L = 0, int R = 0) {
    hungary::L = L;
    hungary::R = R;
    for (int u = 1; u <= L; ++u) G[u].clear();
  }

  bool match(int u) {
    for (int i = 0; i < G[u].size(); ++i) {
      int v = G[u][i];
      if (!mark[v]) {
        mark[v] = true;
        if (!left[v] || match(left[v])) {
          left[v] = u;
          right[u] = v;
          return true;
        }
      }
    }
    return false;
  }

  void solve() {
    memset(left, 0, sizeof left);
    memset(right, 0, sizeof right);

    int ans = 0;
    for (int u = 1; u <= L; ++u)
      if (!right[u]) {
        memset(mark, 0, sizeof mark);
        if (match(u)) ++ans;
      }

    memset(mark, 0, sizeof mark);
    mark[0] = true;
    for (int o = 1; o <= L; ++o)
      if (!mark[o]) {
        mark[o] = true;
        printf("%d", o);
        for (int u = right[o]; !mark[u]; u = right[u]) {
          mark[u] = true;
          printf(" %d", u);
        }
        putchar('\n');
      }
    printf("%d\n", L - ans);
  }
};   // namespace hungary

inline int read() {
  bool positive = true;
  char c = getchar();
  int s = 0;
  for (; c < '0' || c > '9'; c = getchar())
    if (c == '-') positive = false;
  for (; c >= '0' && c <= '9'; c = getchar()) s = s * 10 + c - '0';
  return positive ? s : -s;
}

int main() {
  int N = read();
  int M = read();

  hungary::init(N, N);
  for (int i = 1; i <= M; ++i) {
    int u = read();
    int v = read();
    hungary::G[u].push_back(v);
  }

  hungary::solve();
  return 0;
}

04 魔术球问题
¶

题目链接： Power OJ/1739

经典的有向无环图最小路径覆盖问题：

同样地，拆点得到二分图结构
如果 $μ$ 是左侧的点， $ν$ 是右侧的点，且 $μ + ν$ 是一个完全平方数，那么连一条从 $μ$ 到 $ν$ 的边
逐渐加点，直到最小覆盖数超过给定值终止
假如在 $N + 1$ 的时候终止，可以考虑对于前面 $N$ 个点中会与 $N + 1$ 形成完全平方数的点删掉最后一条边，再跑一遍最大匹配。

路径的问题和 03 类似，此处不再赘述。

04.cpp | 91 lines.

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
#include <bits/stdc++.h>

const int MAXN = 10000 + 10;
const int INF = 0x3f3f3f3f;

namespace hungary {
  int L, R;
  bool mark[MAXN];
  int left[MAXN], right[MAXN];
  std::vector<int> G[MAXN];

  void init(int L = 0, int R = 0) {
    hungary::L = L;
    hungary::R = R;
    for (int u = 1; u <= L; ++u) G[u].clear();
  }

  bool match(int u) {
    for (int i = 0; i < G[u].size(); ++i) {
      int v = G[u][i];
      if (!mark[v]) {
        mark[v] = true;
        if (!left[v] || match(left[v])) {
          left[v] = u;
          right[u] = v;
          return true;
        }
      }
    }
    return false;
  }

  int maxmatch() {
    int ans = 0;
    for (int u = 1; u <= L; ++u)
      if (!right[u]) {
        memset(mark, 0, sizeof mark);
        if (match(u)) ++ans;
      }
    return ans;
  }

  void solve(int N) {
    static std::vector<int> A;
    for (int i = 1; i <= 100; ++i) A.push_back(i * i);
    memset(left, 0, sizeof left);
    memset(right, 0, sizeof right);

    init(N, N);
    for (int i = 1; i <= N; ++i)
      for (auto& a : A)
        if (a - i >= 1 && a - i < i) G[a - i].push_back(i);
    int ans = maxmatch();

    while (true) {
      ++L, ++R;
      for (auto& a : A)
        if (a - L >= 1 && a - L < L) G[a - L].push_back(L);
      ans += maxmatch();
      if (L - ans > N) break;
    }

    for (auto& a : A)
      if (a - L >= 1 && a - L < L) G[a - L].pop_back();
    right[left[L]] = 0;
    --L;
    --R;
    maxmatch();

    printf("%d\n", L);
    memset(mark, 0, sizeof mark);
    mark[0] = true;
    for (int o = 1; o <= L; ++o)
      if (!mark[o]) {
        mark[o] = true;
        printf("%d", o);
        for (int u = right[o]; !mark[u]; u = right[u]) {
          mark[u] = true;
          printf(" %d", u);
        }
        putchar('\n');
      }
  }
};   // namespace hungary

int main() {
  int N;
  std::cin >> N;
  hungary::solve(N);
  return 0;
}

05 圆桌问题
¶

题目链接： Power OJ/1740

经典的二分图多重匹配问题：

将不同单位作为左侧点，不同圆桌作为右侧点，每个左侧点与每个右侧点连接一条容量为 $1$ 的边
建立源点 $s$ ，并从 $s$ 向所有的左侧点引一条容量为 $c a p_{i}$ （第 $i$ 个单位的人数）的边
建立汇点 $t$ ，并从所有的右侧点向 $t$ 引一条容量为 $c a p_{j}$ （第 $j$ 张圆桌的容量）的边跑最大流。
若满流，则有解，方案仅需考虑每个左侧点引出的满流边即可
若不能满流，则无解

05.cpp | 53 lines.

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
#include "./isap.hpp"
#include <bits/stdc++.h>

void ISAP::solve(int M, int N, int tot) {
  s = 0;
  t = M + N + 1;
  n = M + N + 2;
  int ans = maxflow();
  if (ans < tot) {
    puts("0");
    return;
  }

  puts("1");
  for (int o = 1; o <= M; ++o) {
    for (auto& i : G[o]) {
      Edge& e = edges[i];
      if (e.cap > 0 && e.cap == e.flow) printf("%d ", e.to - M);
    }
    printf("\n");
  }
}

inline int read() {
  bool positive = true;
  char c = getchar();
  int s = 0;
  for (; c < '0' || c > '9'; c = getchar())
    if (c == '-') positive = false;
  for (; c >= '0' && c <= '9'; c = getchar()) s = s * 10 + c - '0';
  return positive ? s : -s;
}

int main() {
  int M = read();
  int N = read();
  int tot = 0;

  for (int i = 1; i <= M; ++i) {
    int val = read();
    tot += val;
    ISAP::addedge(0, i, val);
    for (int j = 1; j <= N; ++j) ISAP::addedge(i, M + j, 1);
  }

  for (int i = 1; i <= N; ++i) {
    int val = read();
    ISAP::addedge(M + i, N + M + 1, val);
  }

  ISAP::solve(M, N, tot);
  return 0;
}

06 最长递增子序列问题
¶

题目链接： Power OJ/1741

经典的最多最长不相交路径问题：

不妨记第 $i$ 个数大小为 $A_{i}$ 。为了保证每个点只使用一次，可以拆点：不妨假设原序列第 $i$ 个数对应点 $x_{i}$ ，将其拆成 $x_{i}$ 和 $x_{i}^{'}$ 。

定义 $d p_{i}$ 为以第 $i$ 个数为结尾的最长上升子序列的长度， $O (N^{2})$ 的动态规划
记最长上升子序列长度为 $a n s = max {d p_{i} | 1 ⩽ i ⩽ N}$
- 对于任意 $1 ⩽ i ⩽ N$ ，从 $x_{i}$ 向 $x_{i}^{'}$ 引一条容量为 $1$ 的边（以保证第 $i$ 个数只使用一次）
- 若 $A_{i} < A_{j}$ 且 $d p [i] + 1 = d p [j]$ ，则从 $x_{i}^{'}$ 向 $x_{j}$ 引一条容量为 1 的边
- 建立源点 $s$ ，从 $s$ 向 ${x_{i} | 1 ⩽ i ⩽ N$ 且 $d p_{i} = 1}$ 引一条容量为 $1$ 的边
- 建立汇点 $t$ ，从 ${x_{i}^{'} | 1 ⩽ i ⩽ N$ 且 $d p_{i} = a n s}$ 向 $t$ 引一条容量为 $1$ 的边
然后跑最大流即可
在 2. 的基础上，仅需将从源点出发的边及到达汇点的边（不包括反向边）的容量全改为无穷即可

原题描述不严谨，如果第一问答案为 $2$ ，第三问中，方案 ${x_{1}, x_{N}}$ 只能记做一次。最后需要注意的是，当 $N = 1$ 时，第三问要特判。

06.cpp | 74 lines.

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
#include "./isap.hpp"
#include <bits/stdc++.h>

inline int read() {
  bool positive = true;
  char c = getchar();
  int s = 0;
  for (; c < '0' || c > '9'; c = getchar())
    if (c == '-') positive = false;
  for (; c >= '0' && c <= '9'; c = getchar()) s = s * 10 + c - '0';
  return positive ? s : -s;
}

const int MAXN = 400 + 10;
const int INF = 0x3f3f3f3f;

int dp[MAXN], in[MAXN];


int main() {
  int N = read();
  for (int i = 1; i <= N; ++i) in[i] = read();

  for (int i = 1; i <= N; ++i)
    for (int j = 0; j < i; ++j)
      if (in[i] > in[j]) dp[i] = std::max(dp[i], dp[j] + 1);

  int ans = 0;
  for (int i = 1; i <= N; ++i) ans = std::max(ans, dp[i]);
  printf("%d\n", ans);

  for (int i = 1; i <= N; ++i) {
    if (dp[i] == 1) ISAP::addedge(0, i << 1, INF);
    ISAP::addedge(i << 1, i << 1 | 1, 1);
    if (dp[i] == ans) ISAP::addedge(i << 1 | 1, 1, INF);
  }

  for (int i = 1; i <= N; ++i)
    for (int j = i + 1; j <= N; ++j)
      if (in[i] < in[j] && dp[i] + 1 == dp[j])
        ISAP::addedge(i << 1 | 1, j << 1, 1);

  ISAP::s = 0;
  ISAP::t = 1;
  ISAP::n = N + 1 << 1;

  printf("%d\n", ISAP::maxflow());

  if (ans == 1) {
    printf("%d\n", N);
    return 0;
  }

  for (auto& e : ISAP::edges) e.flow = 0;
  for (auto& i : ISAP::G[2]) {
    auto& e = ISAP::edges[i];
    if (e.to == 3) {
      e.cap = INF;
      break;
    }
  }

  for (auto& i : ISAP::G[N << 1]) {
    auto& e = ISAP::edges[i];
    if (e.to == (N << 1 | 1)) {
      e.cap = INF;
      break;
    }
  }

  printf("%d\n", ISAP::maxflow());

  return 0;
}

07 试题库
¶

题目链接： COGS/732

类似 05，经典的二分图多重匹配问题。

将每道题与其所属类型连接一条容量为 $1$ 的边
建立源点 $s$ ，从 $s$ 向每道试题引一条容量为 $1$ 的边
建立汇点 $t$ ，从每个类型向 $t$ 引一条容量为该类型所需要的题数的边

跑最大流，仅当流量为所有类型所需要的题数总和时有解。

07.cpp | 59 lines.

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
#include "./isap.hpp"
#include <bits/stdc++.h>

void ISAP::solve(int K, int N, int limit) {
  s = 0;
  t = N + K + 1;
  n = N + K + 2;
  if (maxflow() != limit) {
    puts("NoSolution!");
    return;
  }
  for (int o = 1; o <= K; ++o) {
    printf("%d:", o);
    for (int i = 0; i < G[N + o].size(); ++i) {
      Edge& e = edges[G[N + o][i]];
      if (e.to <= N && e.flow == -1) printf(" %d", e.to);
    }
    putchar('\n');
  }
}

inline int read() {
  bool positive = true;
  char c = getchar();
  int s = 0;
  for (; c < '0' || c > '9'; c = getchar())
    if (c == '-') positive = false;
  for (; c >= '0' && c <= '9'; c = getchar()) s = s * 10 + c - '0';
  return positive ? s : -s;
}

const int MAXN = 400 + 10;
const int INF = 0x3f3f3f3f;

int main() {
  freopen("testlib.in", "r", stdin);
  freopen("testlib.out", "w", stdout);
  int K = read();
  int N = read();
  int limit = 0;

  for (int i = 1; i <= K; ++i) {
    int val = read();
    limit += val;
    ISAP::addedge(N + i, N + K + 1, val);
  }

  for (int i = 1; i <= N; ++i) {
    ISAP::addedge(0, i, 1);
    int M = read();
    while (M--) {
      int j = read();
      ISAP::addedge(i, N + j, 1);
    }
  }

  ISAP::solve(K, N, limit);
  return 0;
}

08 机器人路径规划问题
¶

题目链接： Power OJ/1743

暂缺。

09 方格取数问题
¶

题目链接： Power OJ/1744

经典的二分图点权最大独立集。

将方格二染色得到二分图
对于左侧的点，向其对应方格的前后左右方格对应的点连接一条容量为 $\infty$ 的边
建立源点 $s$ ，从 $s$ 向左侧的点分别引一条容量为该点所对应的方格中的数的边
建立汇点 $t$ ，从右侧的点分别引一条容量为该店所对应的方格中的数的边

跑最大流，方格中的数的和 - 最大流量即是答案。

09.cpp | 35 lines.

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
#include "./isap.hpp"
#include "./read.hpp"
#include <bits/stdc++.h>

const int INF = 0x3f3f3f3f;

int main() {
  int row = read();
  int col = read();
  int tot = 0;
  int idx = 0;

  for (int r = 1; r <= row; ++r)
    for (int c = 1; c <= col; ++c) {
      ++idx;
      int val = read();
      tot += val;
      if ((r + c) & 1)
        ISAP::addedge(idx, row * col + 1, val);
      else {
        ISAP::addedge(0, idx, val);
        if (c > 1) ISAP::addedge(idx, idx - 1, INF);
        if (r > 1) ISAP::addedge(idx, idx - col, INF);
        if (c < col) ISAP::addedge(idx, idx + 1, INF);
        if (r < row) ISAP::addedge(idx, idx + col, INF);
      }
    }

  ISAP::s = 0;
  ISAP::t = row * col + 1;
  ISAP::n = row * col + 2;

  printf("%d\n", tot - ISAP::maxflow());
  return 0;
}

10 餐巾计划问题
¶

题目链接： Power OJ/1745

最小费用最大流。

设第 $i$ 天有 $A_{i}$ 条脏毛巾（可以是之前的脏毛巾累积下来的），需要 $B_{i}$ 条干净的毛巾。将第 $i$ 天拆成两个点 $α_{i}$ ， $β_{i}$ 。

建立源点 $s$
- 从 $s$ 向 $α_{i}$ 引一条容量为 $B_{i}$ 、单位流量费用为零的边（表示每天会产生 $B_{i}$ 条脏毛巾）
- 从 $s$ 向 $β_{i}$ 引一条容量为 $B_{i}$ （或者大于等于 $B_{i}$ 皆可）、 单位流量费用为新毛巾的费用的边（表示每天可以购买的新毛巾数）
建立汇点 $t$
- 从 $β_{i}$ 向 $t$ 引一条容量为 $B_{i}$ 、单位流量费用为零 的边（表示每天需要的干净的毛巾数）
如果 $i + m + 1 ⩽ j$ （此 OJ 本题数据有点不一样，应为 $i + m ⩽ j$ ），那么从 $A_{i}$ 向 $B_{j}$ 引一条容量为 $\infty$ （大于 $\sum_{k = 1}^{i} B_{k}$ 即可）、单位流量费用为 $f$ 的边（表示第 $i$ 天快洗可以提供给第 $j$ 天；这里有这样一个事实：如果第 $j + k$ 天需要用到快洗的毛巾，那么大可以将脏毛巾攒到第 $i + k$ 天快洗）；慢洗的连边类似
最后，对于 $i < N$ ，从 $A_{i}$ 向 $A_{i + 1}$ 引一条容量为 $\infty$ 、 单位流量费用为零 的边（表示每天留下来的脏毛巾可以免费留到第二天洗）

跑最小费用最大流即可，由于每天新毛巾可以直接供应 $B_{i}$ 条，因此必然可以满流。最小费用即为答案。

10.cpp | 30 lines.

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
#include "./mcmf.hpp"
#include "./read.hpp"
#include <bits/stdc++.h>

const int INF = 0x3f3f3f3f;

int main() {
  int N = read();
  int p = read();
  int m = read();
  int f = read();
  int n = read();
  int s = read();

  MCMF::init(0, 1);
  for (int i = 1; i <= N; ++i) {
    int val = read();
    MCMF::addedge(0, i << 1, val, 0);
    MCMF::addedge(0, i << 1 | 1, val, p);
    MCMF::addedge(i << 1 | 1, 1, val, 0);
    if (i + 1 <= N) MCMF::addedge(i << 1, (i + 1) << 1, INF, 0);
    if (i + m <= N) MCMF::addedge(i << 1, (i + m) << 1 | 1, INF, f);
    if (i + n <= N) MCMF::addedge(i << 1, (i + n) << 1 | 1, INF, s);
  }

  std::pair<int, int> ans = MCMF::mincostmaxflow();

  printf("%d\n", ans.second);
  return 0;
}

11 航空路线问题
¶

题目链接： Power OJ/1746

最大费用最大流（其实是求两条最长的不相交路径）：

为了保证每个城市只访问一次，需要拆点；不妨将第 $i$ 个城市拆成 $α_{i}$ 和 $β_{i}$ ，且从 $α_{i}$ 向 $β_{i}$ 引一条容量为 1，费用为 1 的边
如果 $i < j$ 且城市 $i$ 和城市 $j$ 之间有直达航线，那么向 $β_{i}$ 和 $α_{j}$ 连接一条容量为 1，费用为 0 的边

跑最大费用最大流（只增广两次），方案根据满流边判断即可。

11.cpp | 85 lines.

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
#include "./mcmf.hpp"
#include "./read.hpp"
#include <bits/stdc++.h>


void MCMF::dfs(std::vector<int>& ans, int o) {
  ans.push_back(o >> 1);
  for (auto& i : G[o]) {
    Edge& e = edges[i];
    if (e.flow == 1) dfs(ans, e.to | 1);
  }
}

bool MCMF::solve(std::string* in) {
  static std::vector<int> ans[2];
  for (int i = 0; i < 2; ++i) {
    if (!spfa()) return false;
    for (int o = t; o != s;) {
      edges[path[o]].flow += 1;
      edges[path[o] ^ 1].flow -= 1;
      o = edges[path[o]].from;
    }
  }

  for (auto& i : G[3]) {
    Edge& e = edges[i];
    if (e.flow == 2) {
      printf("%d\n", 2);
      std::cout << in[1] << "\n" << in[t >> 1] << "\n" << in[1] << "\n";
      return true;
    }
  }

  ans[0].push_back(s >> 1);
  ans[1].push_back(s >> 1);
  int idx = 0;
  for (auto& i : G[3]) {
    Edge& e = edges[i];
    if (e.flow == 1) {
      dfs(ans[idx++], e.to | 1);
    }
  }

  ans[1].pop_back();
  std::reverse(ans[1].begin(), ans[1].end());
  printf("%d\n", ans[0].size() + ans[1].size() - 1);
  for (auto& a : ans[0]) std::cout << in[a] << "\n";
  for (auto& a : ans[1]) std::cout << in[a] << "\n";
  return true;
}

const int MAXN = 100 + 10;
const int INF = 0x3f3f3f3f;
std::unordered_map<std::string, int> ump;
std::string in[MAXN];

int main() {
  int N = read();
  int M = read();
  for (int i = 1; i <= N; ++i) {
    std::cin >> in[i];
    ump[in[i]] = i;
    if (i == 1 || i == N)
      MCMF::addedge(i << 1, i << 1 | 1, 2, -1);
    else
      MCMF::addedge(i << 1, i << 1 | 1, 1, -1);
  }

  for (int i = 1; i <= M; ++i) {
    std::string s, t;
    std::cin >> s >> t;
    int ids = ump[s];
    int idt = ump[t];
    if (ids > idt) std::swap(ids, idt);
    if (ids == 1 && idt == N)
      MCMF::addedge(ids << 1 | 1, idt << 1, 2, 0);
    else
      MCMF::addedge(ids << 1 | 1, idt << 1, 1, 0);
  }

  MCMF::s = 1 << 1;
  MCMF::t = N << 1 | 1;
  if (!MCMF::solve(in)) puts("No Solution!");
  return 0;
}

12 软件补丁问题
¶

题目链接： Power OJ/1747

更像一个状压 $d p$ 。抽象出图的结构，跑最短路即可。

定义 $s$ 为当前软件的错误状态，如果 $s$ 中包含 $B 1 [i]$ 的所有错误，且不包含 $B 2 [i]$ 中的所有错误，那么存在一条从 $s$ 到 $s - F 1 [i] + F 2 [i]$ （这里的 - 指集合运算），且花费为 $c o s t [i]$ 的边。

12.cpp | 95 lines.

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
#include <bits/stdc++.h>

namespace solve {
  const int INF = 0x3f3f3f3f;
  const int MAXN = (1 << 20) + 10;

  struct node {
    int B1, B2;
    int F1, F2;
    int cost;
    node(int B1 = 0, int B2 = 0, int F1 = 0, int F2 = 0, int cost = 0)
        : B1(B1), B2(B2), F1(F1), F2(F2), cost(cost) {
    }
  };

  int s, t;
  int dist[MAXN];
  std::vector<node> nodes;

  void update(char* s, int& x, int& y) {
    x = y = 0;
    for (int i = 0; s[i]; ++i) {
      if (s[i] == '+')
        x |= 1 << i;
      else if (s[i] == '-')
        y |= 1 << i;
    }
  }

  int spfa() {
    static bool inq[MAXN];
    static std::queue<int> Q;

    memset(dist, 0x3f, sizeof dist);

    Q.push(s);
    dist[s] = 0;
    inq[s] = true;

    while (!Q.empty()) {
      int o = Q.front();
      Q.pop();
      for (auto& e : nodes) {
        if ((o & e.B1) == e.B1 && (o & e.B2) == 0) {
          int u = (o & e.F1) | e.F2;
          if (dist[u] > dist[o] + e.cost) {
            dist[u] = dist[o] + e.cost;
            if (!inq[u]) {
              inq[u] = true;
              Q.push(u);
            }
          }
        }
      }
      inq[o] = false;
    }

    return dist[t] != INF ? dist[t] : 0;
  }

};   // namespace solve

inline int read() {
  bool positive = true;
  char c = getchar();
  int s = 0;
  for (; c < '0' || c > '9'; c = getchar())
    if (c == '-') positive = false;
  for (; c >= '0' && c <= '9'; c = getchar()) s = s * 10 + c - '0';
  return positive ? s : -s;
}

int main() {
  int N = read();
  int M = read();
  int B1, B2, F1, F2, cost, re;
  char in[100];

  re = (1 << N) - 1;
  for (int i = 0; i < M; ++i) {
    cost = read();
    scanf("%s", in);
    solve::update(in, B1, B2);
    scanf("%s", in);
    solve::update(in, F2, F1);
    F1 = re ^ F1;
    solve::nodes.push_back(solve::node(B1, B2, F1, F2, cost));
  }

  solve::s = re;
  solve::t = 0;
  printf("%d\n", solve::spfa());

  return 0;
}

Summary
¶

#	Problem	Category	Solution / Code
01	飞行员配对方案问题	二分图最大匹配	01
02	太空飞行计划问题	最大权闭合图	02
03	最小路径覆盖问题	最小路径覆盖	03
04	Power OJ/1739	最小路径覆盖	04
05	Power OJ/1740	二分图多重匹配	05
06	Power OJ/1741	最多最长不相交路径	06
07	COGS/732	二分图多重匹配	07
08	Power OJ/1743	暂缺	08
09	Power OJ/1744	二分图点权最大独立集	09
10	Power OJ/1745	最小费用最大流（难在建图）	10
11	Power OJ/1746	最大费用最大流	11
12	Power OJ/1747	最短路	12

网络流基础之最大权闭合图

Prepare¶

Problems¶

01 飞行员配对方案问题¶

02 太空飞行计划问题¶

03 最小路径覆盖问题¶

04 魔术球问题¶

05 圆桌问题¶

06 最长递增子序列问题¶

07 试题库¶

08 机器人路径规划问题¶

09 方格取数问题¶

10 餐巾计划问题¶

11 航空路线问题¶

12 软件补丁问题¶

Summary¶

Related¶