网络流题集

最大流

Luogu-P1231 教辅的组成

三倍经验： Luogu-P1402 酒店之王 / Luogu-P2891 [USACO07OPEN] Dining G

一眼丁真建图：S->练习册->书->答案->T

然而是错的。很明显，书有可能被多次匹配，与题意不符。

正确的建图：S->练习册->书（拆点）->答案->T

为什么中间层的书要拆点呢？因为一本书不能被重复选用。我们的目的是保证一本书流出的流量只能是 $1$。所以我们把每个代表书的点拆成两个点，左边的点和练习册连边，右边的点和答案连边；左右对应点之间也要连一条容量为 $1$ 的边。

Luogu-P2764 最小路径覆盖问题

定理：最小路径覆盖数=$|G|$-二分图最大匹配数

首先我们假设现在原图内每个点都是一条路径，此时最少路径数为 $n$。

考虑合并路径，当且仅当两条路径首尾相连的时候可以合并。

将点 $x$ 拆成出点 $x$ 和入点 $x+n$，当我们连接 $u, v$ 时，转化为连接 $u, v+n$。将 $S$ 与所有 $u$ 连边，将所有 $u+n$ 与 $T$ 连边。所有边的容量都为 $1$。

在一开始每个点都是一条独立的路径，每次合并将两条路径合并为一条路径，那么最终路径即为点数减去最大匹配数，这样求得的路径覆盖即为最小路径覆盖。

对于输出路径，用 to 记录下一个节点，tag 标记该节点前面是否还有点。

 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

ll dfs(int u, int t, ll flow) {
  if (u == t) return flow;
  ll ans = 0;
  vis[u] = 1;
  for (int &i = cur[u]; ~i; i = e[i].nxt) {  // i 用引用：当前弧优化
    int v = e[i].to;
    if (!vis[v] && dep[v] == dep[u] + 1 && e[i].cap > e[i].flow) {
      ll d = dfs(v, t, min(flow - ans, e[i].cap - e[i].flow));
      if (!d) continue;
      ans += d;
      e[i].flow += d;
      e[i ^ 1].flow -= d;
      to[u] = v;
      if (u != S) { tag[v - n] = 1; }
      if (ans == flow) break;  // 剪枝，残余流量用尽，停止增广
    }
  }
  vis[u] = 0;
  return ans;
}
ll Dinic(int s, int t) {
  ll ret = 0;
  while (bfs(s, t)) {
    memcpy(cur, fir, sizeof cur);
    ret += dfs(s, t, INF);
  }
  for (int i = 1; i <= n; i++) {
    if (tag[i] == 0) {
      cout << i << " ";
      int x = i;
      while (to[x] && to[x] != t) {
        cout << to[x] - n << " ";
        x = to[x] - n;
      }
      cout << "\n";
    }
  }
  return ret;
}
int main() {
  ios::sync_with_stdio(false);

  memset(fir, -1, sizeof fir);
  cin >> n >> m;
  S = 2 * n + 1, T = S + 1;
  for (int i = 0; i < m; i++) {
    int x, y;
    cin >> x >> y;
    addEdge(x, y + n, 1);
  }
  for (int i = 1; i <= n; i++) {
    addEdge(S, i, 1);
    addEdge(i + n, T, 1);
  }
  int t = Dinic(S, T);
  cout << n - t << endl;
  return 0;
}

最小割

方格取数问题

对矩阵进行黑白染色，那么比如选了一个黑格，那么与它相邻的白格不能选。可以计算不选的方格，其余的都选。容易想到最小割。

那么建图就很容易了。对于每个点 $(i,j)$，数值为 $a_{i,j}$，如果是白色点，那么从源点向它连一条容量 $a_{i,j}$ 的边；否则就从这个点向汇点连一条容量 $a_{i,j}$ 的边。这样我们就把不选的点转化成了割掉的边。为了保证相邻点直接的边不会被割掉，我们从每个白点向与其相邻的黑点连容量为 $INF$ 的边（他们之间的边只从白连到黑，避免重复计算）。答案为全局和减去最小割。

Luogu-P2598 [ZJOI2009] 狼和羊的故事

原点向所有狼连容量 $INF$ 的边，所有羊向汇点连容量 $INF$ 的边，所有点向四周连容量为 $1$ 的边。

最小割即为答案，因为狼和羊之间的边都被割掉了。

Luogu-P1361 小M的作物

二者取其一模型。

考虑点集 ${u, v, w}$ 对集合 $A$ 的贡献，加入其中一者被割进 $B$，那这个点集就没有贡献，即点集与 $A$ 的连边要割掉。

用一个虚点 $x$ 从 $S$ 连一条边代表贡献，如果其中一个点被割进了集合 $B$，那这条代表贡献的边也要割掉，而 $x$ 到 $u, v, w$ 的边不能断开。所以 $(S, x)$ 的容量为 $c$，$(x, u), (x, v), (x, w)$ 的容量都是 $INF$（保证不被断开）。

答案为总收益减去最小割。

Luogu-P2762 太空飞行计划问题

两倍经验：Luogu-P3410 拍照

最大权值闭合图模型。

Luogu-P4177 [CEOI2008] order

如果没有租机器，那这道题就是纯最大权值闭合图模型。

图中对于工作和它所需的机器之间边的容量为 $INF$，所以这条边不可能被割，意义即为选择这个工作就必须购买这个机器。那么租用就可以将这条边的容量改为 $b_{ij}$，可以用 $b_{ij}$ 割掉这条边，表示选择这个工作后，可以花费 $b_{ij}$ 的代价代替购买机器。