图论 cpp 模板

最后更新于：2022年6月25日 下午

图论还是一个特别强的工具。 为什么没有图论的 STL？

以 代码更新汇总 中的代码为主

其他人的图论模板可做参考（其实我自己的够用了目前看）

存边方式

  • 不涉及删边和反边（最简单常用的情况），可以直接用 vector 邻接表 std::vector<std::vector<std::pair<int, T>>>
  • 仅涉及反向边，不涉及删边（如网络流问题），可以使用 vector 版本的链式前向星（写法特别简洁）
  • 不涉及重边（即使涉及重边也可以！其它操作随意，无向图其实也可以操作），都可以使用 vector 邻接表 std::vector<std::unordered_map<int, int>>（更快）或std::vector<std::map<int, T>>，当然了各种操作都要带个 log
  • 如果涉及重边（逻辑上没法合并的那种），就不存在反边的概念了。此时可以用链式前向星，也可以使用 最简单情况的 vector 邻接表（也支持删边，只是比较慢）无论怎么，即使不用链式前向星，这种思想还是值得学习的。

链式前向星 （弃用）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class LinkStar {
 public:
  std::vector<int> head, nxt, to;
  std::vector<LL> w;
  LinkStar(int n) {
    nxt.clear();
    to.clear();
    head = std::vector<int>(n + 1, -1);
  }
  void addedge(int u, int v, LL val) {
    nxt.emplace_back(head[u]);
    head[u] = to.size();
    to.emplace_back(v);
    w.emplace_back(val);
  }
};

邻接矩阵存边（太简单就不写了）

邻接 map or unorder_map 存边（同上）

vector 版本链式前向星（见后面网络流的做法）

树上问题转化成序列问题

无根树的 Prufer 序列

A.Cayley 在 1889 年首先公布并证明 \(n\) 个节点的无根树和长度为 \(n-2\)，数值在 \(1 \to n\) 的序列有一一对应

构造方式：删除编号最小的叶子节点，并记录它的父节点。

\(n\) 个节点的无根树（也就是简单无向图），可以唯一的给出一个长度为 \(n-2\) 的编码，同样每一个长为 \(n-2\) 的编码都可以唯一的产生一棵 \(n\) 个节点的无根树 （这就证明了上面结论）

给定一颗 \(n>2\) 个节点的无根树，每次找出无根树中，度数为 \(1\) 的节点中编号最小的节点 \(A\)，记录节点 \(A\) 的邻接点，然后删除节点 \(A\) 和它的边。这样一直继续下去，直到只剩下两个节点。

度数为 \(i\) 的节点恰好在 Prufer 编码中出现 \(i-1\) 次

给你一个长度为 \(n-2\) 的 Prufer 编码，我们只要找出 没有在当前编码中最小的 跟编码中第一个节点相连即可。重复下去即可得到无根树。

CP-algorithm 中有详细的讲解和代码 无根树 和 Prufer 序列 互转的 \(O(n \log n)\) 和 \(O(n)\) 两类代码。

有根树的 dfs 序

本质作用： 将树上问题转化成序列问题，dfs 序是基础，Euler 序可以认为是推广。

树节点按 dfs 过程中的访问顺序排序（进入记录一次，出去记录一次），称为 dfs 序。处理子树的问题很有用。

这里 给出了 dfs 序的一些应用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class DfsTour {
  int n, cnt;
  std::vector<int> l, r;
  std::vector<std::vector<int>> e;
 public:
  DfsTour(int _n) : n(_n), e(n), l(n), r(n), cnt(0) {}
  void addEdge(int u, int v) {
    if (u == v) return;
    e[u].emplace_back(v);
    e[v].emplace_back(u);
  }
  void dfs(int u, int fa) {
    l[u] = ++cnt;
    for (auto v : e[u]) if (v != fa) {
      dfs(v, u);
    }
    r[u] = cnt;
  }
};

其中 u 的子树的编号正好是区间 \([l_u, r_u]\)，注意不可能有交叉的情况！

关于子树的问题，可以考虑一下 dfs 序。

  1. 在节点权值可修改的情况下，查询某个子树里的所有点权和。

    由于在上述 dfs 序中子树 x 是连续的一段 \([l_x, r_x]\)，所以用树状数组：单点更新，区间查询。

  2. 节点 X 到 Y 的最短路上所有点权都加上一个数 W，查询某个子树里的所有点权和。 可以理解为更新 4 段区间，根节点到 X，根节点到 Y，根节点到 lca(X, Y)，根节点到 fa[lca(X, Y)]，可以用 线段树 或 带区间更新的树状数组。

有根树的 Euler 序列（长度为 2n - 1）

1
2
3
4
5
6
7
8
9
10
11
12
13
// 以 rt 为根的树，只记录进入的 Euler 序（长度为 2n - 1)
std::vector<int> EulerTour(std::vector<std::vector<int>>& e, int rt) {
  std::vector<int> r;
  std::function<void(int, int)> dfs = [&](int u, int fa) -> void {
    r.emplace_back(u);
    for (auto v : e[u]) if (v != fa) {
      dfs(v, u);
      r.emplace_back(u);
    }
  };
  dfs(rt, rt);
  return r;
}

首先观察到这个树的 Euler 序列首尾都是根的编号，如果把首尾连接起来，就会发现：这个序列中元素出现的次数正好是它的度。并且我们可以轻松的换根节点!!!，以谁为根就以谁开始转圈！并且如果删除某个节点，那么就会形成以这个节点为度的个数的连通分支。

问题 1：求 最近公共祖先（LCA）

求完 Euler 序列后，求 lca(u, v) 那就是 \(E[pos[u], \cdots, pos[v]]\) 的最小值，其中 pos[u] 为 u 首次出现在 E 中的标号。那么显然我们可以用线段树 \(O(n)\) 预处理，单步 \(O(\log n)\) 在线查询 lca。

问题 2：求树上任意两点的距离

求完 Euler 序列的同时，我们先求出根节点和其它点的距离，由上述步骤我们能求 lca，那么树上任意两点 \(u, v\) 的距离就是 d[u] + d[v] - d[lca(u, v)]

如果求树上任意两点距离之和：只需统计每条边经过多少次就行，显然等价于每条边左右两边节点个数，就不用上述做法了。

问题 3：求树上节点到根节点的最短路径点权和

树链剖分 Heavy-Light decomposition

重链剖分可以理解为 dfs 序和 Euler 序的增强优化拓展版本。

重链剖分求 LCA 的模板例题：LOJ 3379，我的实现

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
#include <bits/stdc++.h>
#define watch(x) std::cout << (#x) << " is " << (x) << std::endl
using LL = long long;
using namespace std;

// 为了代码简洁，树的编号以 1 开始
class LCA {
  int n;
  std::vector<int> fa, dep, sz, son, top;
 public:
  LCA(std::vector<std::vector<int>> &e, int rt = 1) : n(e.size()) {
    fa.resize(n);
    dep.resize(n);
    sz.resize(n);
    son.resize(n);
    fa[rt] = rt;
    dep[rt] = 0;
    std::function<int(int)> pdfs = [&](int u) -> int {
      sz[u] = 1;
      for (auto v : e[u]) if (v != fa[u]) {
        dep[v] = dep[u] + 1;
        fa[v] = u;
        sz[u] += pdfs(v);
        if (sz[v] > sz[son[u]]) son[u] = v;
      }
      return sz[u];
    };
    top.resize(n);
    std::function<void(int, int)> dfs = [&](int u, int t) -> void {
      top[u] = t;
      if (son[u] == 0) return;
      dfs(son[u], t);
      for (auto v : e[u]) if (v != fa[u] && v != son[u]) dfs(v, v);
    };
    pdfs(rt);
    dfs(rt, rt);
  }
  int lca(int u, int v) {
    while (top[u] != top[v]) {
      if (dep[top[u]] > dep[top[v]]) {
        u = fa[top[u]];
      } else {
        v = fa[top[v]];
      }
    }
    return dep[u] < dep[v] ? u : v;
  }
};

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int n, m, rt;
  std::cin >> n >> m >> rt;
  std::vector<std::vector<int>> e(n + 1);
  for (int i = 1; i < n; ++i) {
    int u, v;
    std::cin >> u >> v;
    e[u].emplace_back(v);
    e[v].emplace_back(u);
  }
  LCA g(e, rt);
  for (int i = 0; i < m; ++i) {
    int x, y;
    std::cin >> x >> y;
    std::cout << g.lca(x, y) << "\n";
  }
  return 0;
}

重链剖分求任意两点路径上所有节点的点权和，求子树的点权和（利用 dfs 编号和 sz 直接区间查询或区间修改）

例题：LOJ 3384，参考：ChinHhh's blog，用加强版树状数组而非线段树算的：提交记录。

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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
#include <bits/stdc++.h>
#define watch(x) std::cout << (#x) << " is " << (x) << std::endl
using LL = long long;

LL M;
struct TreeArray {
  std::vector<LL> s;
  TreeArray() {}
  TreeArray(int n) : s(n + 1) {}
  int lowbit(int n) {
    return n & (-n);
  }
  void add(int id, int p) {
    while (id < s.size()) {
      (s[id] += p) %= M;
      id += lowbit(id);
    }
  }
  LL sum(int id) {
    LL r = 0;
    while (id) {
      (r += s[id]) %= M;
      id -= lowbit(id);
    }
    return r;
  }
};
class TreeArrayPlus {
  int n;
  // c[i] = a[i] - a[i - 1], b_i = (i - 1) * c_i
  TreeArray B, C;
  void add(int id, int p) {
    C.add(id, p);
    B.add(id, (id - 1) * p % M);
  }
 public:
  TreeArrayPlus() {}
  TreeArrayPlus(int _n) : n(_n), B(n), C(n) {}
  void add(int l, int r, int p) {
    add(l, p);
    add(r + 1, -p);
  }
  LL sum(int id) {
    return (id * C.sum(id) + M - B.sum(id)) % M;
  }
  LL sum(int l, int r) {
    return ((sum(r) - sum(l - 1)) % M + M) % M;
  }
};
// 为了代码简洁，树的编号以 1 开始
class HLD {
  int n;
  std::vector<int> fa, dep, sz, son, top, dfn;
  TreeArrayPlus Tree;
 public:
  HLD(std::vector<std::vector<int>> &e, std::vector<int> &a, int rt = 1) : n(e.size()), Tree(n + 1) {
    fa.resize(n);
    dep.resize(n);
    sz.resize(n);
    son.resize(n);
    fa[rt] = dep[rt] = 0;
    std::function<int(int)> pdfs = [&](int u) -> int {
      sz[u] = 1;
      for (auto v : e[u]) if (v != fa[u]) {
        dep[v] = dep[u] + 1;
        fa[v] = u;
        sz[u] += pdfs(v);
        if (sz[v] > sz[son[u]]) son[u] = v;
      }
      return sz[u];
    };
    top.resize(n);
    dfn.resize(n);
    int cnt = 0;
    std::function<void(int, int)> dfs = [&](int u, int t) -> void {
      top[u] = t;
      dfn[u] = ++cnt;
      if (son[u] == 0) return;
      dfs(son[u], t);
      for (auto v : e[u]) if (v != fa[u] && v != son[u]) dfs(v, v);
    };
    pdfs(rt);
    dfs(rt, rt);
    for (int i = 1; i < n; ++i) Tree.add(dfn[i], dfn[i], a[i]);
  }
  // u 到根的最短路径上所有边权值加 c
  void add(int u, int c) {
    while (u) {
      Tree.add(dfn[top[u]], dfn[u], c);
      u = fa[top[u]];
    }
  }
  // u 到根的最短路径上所有边权值之和
  LL query(int u) {
    LL r = 0;
    while (u) {
      r += Tree.sum(dfn[top[u]], dfn[u]);
      u = fa[top[u]];
    }
    return r % M;
  }
  // u, v 的最短路径上所有边权值加 c（可以通过 lca 和根来搞，但是会很慢）
  void add(int u, int v, int c) {
    while (top[u] != top[v]) {
      if (dep[top[u]] > dep[top[v]]) {
        Tree.add(dfn[top[u]], dfn[u], c);
        u = fa[top[u]];
      } else {
        Tree.add(dfn[top[v]], dfn[v], c);
        v = fa[top[v]];
      }
    }
    if (dep[u] < dep[v]) {
      Tree.add(dfn[u], dfn[v], c);
    } else {
      Tree.add(dfn[v], dfn[u], c);
    }
  }
  // u, v 的最短路径上所有边权值之和（可以通过 lca 和根来搞，但是会很慢）
  LL query(int u, int v) {
    LL r = 0;
    while (top[u] != top[v]) {
      if (dep[top[u]] > dep[top[v]]) {
        r += Tree.sum(dfn[top[u]], dfn[u]);
        u = fa[top[u]];
      } else {
        r += Tree.sum(dfn[top[v]], dfn[v]);
        v = fa[top[v]];
      }
    }
    if (dep[u] < dep[v]) {
      r += Tree.sum(dfn[u], dfn[v]);
    } else {
      r += Tree.sum(dfn[v], dfn[u]);
    }
    return r % M;
  }
  void addSon(int u, int c) {
    Tree.add(dfn[u], dfn[u] + sz[u] - 1, c);
  }
  LL querySon(int u) {
    return Tree.sum(dfn[u], dfn[u] + sz[u] - 1);
  }
  int lca(int u, int v) {
    while (top[u] != top[v]) {
      if (dep[top[u]] > dep[top[v]]) {
        u = fa[top[u]];
      } else {
        v = fa[top[v]];
      }
    }
    return dep[u] < dep[v] ? u : v;
  }
};

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int n, m, rt;
  std::cin >> n >> m >> rt >> M;
  std::vector<int> a(n + 1);
  for (int i = 1; i <= n; ++i) std::cin >> a[i];
  std::vector<std::vector<int>> e(n + 1);
  for (int i = 1; i < n; ++i) {
    int u, v;
    std::cin >> u >> v;
    e[u].emplace_back(v);
    e[v].emplace_back(u);
  }
  HLD g(e, a, rt);
  for (int i = 0; i < m; ++i) {
    int op, x, y, z;
    std::cin >> op;
    if (op == 1) {
      std::cin >> x >> y >> z;
      g.add(x, y, z);
    } else if (op == 2) {
      std::cin >> x >> y;
      std::cout << g.query(x, y) << "\n";
    } else if (op == 3) {
      std::cin >> x >> z;
      g.addSon(x, z);
    } else {
      std::cin >> x;
      std::cout << g.querySon(x) << "\n";
    }
  }
  // auto start = std::clock();
  // std::cout << "Time used: " << (std::clock() - start) << "ms" << std::endl;
  return 0;
}

长链剖分优化 DP，例题：1009F

这个题显然可以用重链剖分来做，或者说下面的 dsu on tree 来做（\(O(n \log n)\)），但是官方题解 用长链剖分可以优化到 \(O(n)\)！太强了。主要原因是因为，每个轻儿子节点最多被合并一次（它第一次合并之后，它的信息就被和他同深度的重兄弟节点给吸收了），后面再合并的时候就不算它被合并而算当前重儿子节点的合并了（妙不可言）。但是父节点占据儿子节点的时候有个问题就是用 std::map 或 std::unordered_map 本质上都会带一个 log，因此我们需要用 vector 保存信息。

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
#include <bits/stdc++.h>
#define watch(x) std::cout << (#x) << " is " << (x) << std::endl
using LL = long long;

#include <bits/stdc++.h>
#define watch(x) std::cout << (#x) << " is " << (x) << std::endl
using LL = long long;

// 为了代码简洁，树的编号以 1 开始。
std::vector<int> dsuOnTree(std::vector<std::vector<int>> &e, int rt = 1) {
  int n = e.size();
  // 预处理出重儿子
  std::vector<int> sz(n), son(n);
  std::function<void(int, int)> pdfs = [&](int u, int fa) -> void {
    for (auto v : e[u]) if (v != fa) {
      pdfs(v, u);
      if (sz[v] > sz[son[u]]) son[u] = v;
    }
    sz[u] = sz[son[u]] + 1;
  };
  std::vector<int> ans(n);
  std::function<std::vector<int>(int, int)> dfs = [&](int u, int fa) -> std::vector<int> {
    if (son[u] == 0) {
      ans[u] = 0;
      return {1};
    }
    auto a = dfs(son[u], u);
    ans[u] = ans[son[u]];
    for (auto v : e[u]) if (v != fa && v != son[u]) {
      auto tmp = dfs(v, u);
      // 这里需要对齐
      for (int ai = a.size() - 1, ti = tmp.size() - 1; ti >= 0; --ti, --ai) {
        a[ai] += tmp[ti];
        if (a[ai] > a[ans[u]] || (a[ai] == a[ans[u]] && ai > ans[u])) {
          ans[u] = ai;
        }
      }
    }
    a.emplace_back(1);
    if (a[ans[u]] == 1) ans[u] = sz[u] - 1;
    return a;
  };
  pdfs(rt, 0);
  dfs(rt, 0);
  for (int i = 1; i < n; ++i) ans[i] = sz[i] - 1 - ans[i];
  return ans;
}

int main() {
  //freopen("in", "r", stdin);
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int n;
  std::cin >> n;
  std::vector<std::vector<int>> e(n + 1);
  for (int i = 1; i < n; ++i) {
    int u, v;
    std::cin >> u >> v;
    e[u].emplace_back(v);
    e[v].emplace_back(u);
  }
  auto r = dsuOnTree(e);
  for (int i = 1; i <= n; ++i) std::cout << r[i] << "\n";
  return 0;
}

树上启发式算法（dsu on tree）

先处理轻儿子，但是不保留影响，再处理重儿子保留，再暴力处理所有其它情况，再看次节点是否需要保留。

复杂度分析真的太妙了！

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
// 为了代码简洁，树的编号以 1 开始，参考：https://www.cnblogs.com/zwfymqz/p/9683124.html
std::vector<LL> dsuOnTree(std::vector<std::vector<int>> &e, std::vector<int> &a, int rt = 1) {
  int n = a.size();
  // 预处理出重儿子
  std::vector<int> sz(n), son(n), cnt(n);
  std::function<int(int, int)> pdfs = [&](int u, int fa) -> int {
    sz[u] = 1;
    for (auto v : e[u]) if (v != fa) {
      sz[u] += pdfs(v, u);
      if (sz[v] > sz[son[u]]) son[u] = v;
    }
    return sz[u];
  };
  // 这个函数具体问题具体分析
  std::vector<LL> ans(n);
  int mx = 0, Son = 0;
  LL sm = 0;
  std::function<void(int, int)> deal = [&](int u, int fa) -> void {
    ++cnt[a[u]];
    if (cnt[a[u]] > mx) {
      mx = cnt[a[u]];
      sm = a[u];
    } else if (cnt[a[u]] == mx) {
      sm += a[u];
    }
    for (auto v : e[u]) if (v != fa && v != Son) {
      deal(v, u);
    }
  };
  std::function<void(int, int)> del = [&](int u, int fa) -> void {
    --cnt[a[u]];
    for (auto v : e[u]) if (v != fa) del(v, u);
  };
  std::function<void(int, int, bool)> dfs = [&](int u, int fa, bool save) -> void {
    for (auto v : e[u]) if (v != fa && v != son[u]) {
      dfs(v, u, 0); // 先计算轻边贡献，但最终要消除影响，防止轻边互相干扰
    }
    if (son[u]) dfs(son[u], u, 1);  // 统计重儿子的贡献，但不消除影响
    Son = son[u];
    deal(u, fa); // 暴力处理除重儿子外的贡献
    Son = 0;
    ans[u] = sm;
    if (!save) {
      del(u, fa);
      sm = 0;
      mx = 0;
    }
  };
  pdfs(rt, rt);
  dfs(rt, rt, 1);
  return ans;
}

思想是这样的，到时候具体问题灵活运用，不必死套模板，例如 gym 102832F 我的另样做法 submission 105273241 更加优秀，快速。

树上问题

树的直径：先从任意点开始寻找最远距离点（bfs 遍历一下），然后再找一次就是了（易证）

例题：1405D

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
std::vector<int> d(n);
auto bfs = [&](int x) -> int {
  std::fill(d.begin(), d.end(), -1);
  std::queue<int> Q;
  d[x] = 0;
  Q.push(x);
  while (!Q.empty()) {
    int u = Q.front();
    Q.pop();
    for (auto v : e[u]) if (d[v] == -1) {
      d[v] = d[u] + 1;
      Q.push(v);
    }
  }
  return std::max_element(d.begin(), d.end()) - d.begin();
};

[树的中心]：所有点到该点的最大值最小（直径的中点）

树的重心：去掉这个点后连通分支的节点数量的最大值最小

根据 DFS 子树的大小和“向上”的子树大小就可以知道所有子树中最大的子树节点数。：例题 1406C

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
// 其中 e 表示树的边，n 为数的数量
std::function<int(int)> degree = [&](int u) -> int {
  d[u] = 1;
  for (auto v : e[u]) if (d[v] == -1) {
    d[u] += degree(v);
  }
  return d[u];
};
auto barycenter = [&](int x) {
  std::fill(d.begin(), d.end(), -1);
  int cnt = degree(x);
  std::vector<int> w(n, n);
  std::queue<int> Q;
  Q.push(x);
  while (!Q.empty()) {
    int u = Q.front();
    Q.pop();
    w[u] = cnt - d[u];
    for (auto v : e[u]) if (w[v] == n) {
      w[u] = std::max(w[u], d[v]);
      Q.push(v);
    }
  }
  int r = std::min_element(w.begin(), w.end()) - w.begin();
  return std::make_pair(r, w[r]);
};

最近公共祖先简称 LCA（Lowest Common Ancestor）

  • 策略 1：其中一个节点一直往上标记父辈到根，然后另一个节点往上找父辈，直到找到首次被标记过的节点
  • 策略 2：标记没个节点的深度，深度高的往上到同一层，然后一起一步步上去，直到是公共节点
  • 策略 3：做一次 DFS 得到 Euler 序列，然后就变成找区间最小值问题了（可以使用线段树）
  • 策略 4：树链剖分（见下面做法，目前我的做法）
  • 其他：倍增（记录 fa[u][i]：表示 u 的第\(2^i\)祖先），Tarjan 算法，动态树 OI-wiki 给了很多做法，竟然有标准 \(O(N)\) 时空复杂度的 RMQ 做法还支持在线，太强了，太强了，mark 一下，有模板，但是并不想学。

有向无环图的拓扑排序之 Kahn 算法

给定有向图，然后把节点按照顺序排列，使得任意有向边的起点在终点前。

做法：维护一个入度为 0 的节点队列，丢出队列时它连接的所有点入度减 1，为 0 就加入节点集合。

模板例题：LOJ U107394。

一个有向图是无环图，当且仅当它存在拓扑排序（有重边就用 set 存边自动去重，否则直接用 vector 即可）。

可达性统计问题

这个问题貌似没有很好的做法。 有向无环图的情况：ACWing 164 可达性统计 利用 bitset 做到 \(\frac{N^2}{64}\)

一般的图可以通过先缩点变成有向无环图处理

无向图的 Euler 路 的 Hierholzer 算法

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
// 求字典序最小的 Euler 路，没有的话输出 空（允许重边，不允许就修改成 set）
std::stack<int> EulerPathS(std::vector<std::multiset<int>> e) {
  int cnt = std::count_if(e.begin(), e.end(), [](auto x) {
    return x.size() % 2 == 1;
  });
  if (cnt > 2) return std::stack<int>();
  std::stack<int> ans;
  std::function<void(int)> Hierholzer = [&](int u) {
    while (!e[u].empty()) {
      int v = *e[u].begin();
      e[u].erase(e[u].begin());
      e[v].erase(e[v].find(u));
      Hierholzer(v);
    }
    ans.push(u);
  };
  for (int i = 0; i < e.size(); ++i) {
    if (!e[i].empty() && ((e[i].size() & 1) || (cnt == 0))) {
      Hierholzer(i);
      break;
    }
  }
  return ans;
}
// 求 rt 开头的字典序 Euler 路（保证存在且不允许重边，允许重边就修改成 multiset 即可）
std::stack<int> EulerPath(std::vector<std::set<int>> e, int rt) {
  std::stack<int> ans;
  std::function<void(int)> Hierholzer = [&](int u) {
    while (!e[u].empty()) {
      int v = *e[u].begin();
      e[u].erase(e[u].begin());
      e[v].erase(e[v].find(u));
      Hierholzer(v);
    }
    ans.push(u);
  };
  Hierholzer(rt);
  return ans;
}

有向图的 Hamiltonian 路的启发式算法

笛卡尔树 ：我去，竟然是 \(O(n)\) 复杂度的建树（弃用没必要直接学单调栈即可）

从OI - wiki 中看到的讲解和复杂度分析!，注意到右链是从尾巴往上查找的。 hdu 1506 这就给出了一个 \(O(n)\) 复杂度求出包含 i且以 a[i] 为最大值的区间的方法（最小值保存的时候取负数即可），太强了！ 求上述对应的最大值区间，需要修改 0 节点的值，以及 build 的大于号改成小于号。

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>
#define watch(x) std::cout << (#x) << " is " << (x) << std::endl
#define print(x) std::cout << (x) << std::endl
using LL = long long;
struct Node {
  int id, val, par, ch[2];
  void init(int _id, int _val, int _par) {
    id = _id, val = _val, par = _par, ch[0] = ch[1] = 0;
  }
};
int cartesian_build(std::vector<Node> &tree, int n) {
  for (int i = 1; i <= n; ++i) {
    int k = i - 1;
    while (tree[k].val < tree[i].val) k = tree[k].par;
    tree[i].ch[0] = tree[k].ch[1];
    tree[k].ch[1] = i;
    tree[i].par = k;
    tree[tree[i].ch[0]].par = i;
  }
  return tree[0].ch[1];
}
int main() {
  // freopen("in","r",stdin);
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int n;
  while (std::cin >> n && n) {
    std::vector<Node> tree(n + 1);
    tree[0].init(0, INT_MAX, 0);
    for (int i = 1, x; i <= n; ++i) {
      std::cin >> x;
      tree[i].init(i, x, 0);
    }
    int root = cartesian_build(tree, n);
    LL ans = 0;
    std::function<int(int)> dfs = [&](int x) -> int {
      if (x == 0) return 0;
      int sz = dfs(tree[x].ch[0]);
      sz += dfs(tree[x].ch[1]);
      ans = std::max(ans, LL(sz + 1) * tree[x].val);
      return sz + 1;
    };
    dfs(root);
    std::cout << ans << std::endl;

    // 下面是求以 a[i] 为最大值且包含 i 的最大区间
    std::vector<int> l(n + 1), r(n + 1);
    std::function<void(int)> getinterval = [&](int x) {
      if (x == 0) return;
      if (tree[tree[x].par].ch[0] == x) {
        r[x] = tree[x].par - 1;
        l[x] = l[tree[x].par];
      } else {
        l[x] = tree[x].par + 1;
        r[x] = r[tree[x].par];
      }
      getinterval(tree[x].ch[0]);
      getinterval(tree[x].ch[1]);
    };
    l[root] = 1;
    r[root] = n;
    getinterval(tree[root].ch[0]);
    getinterval(tree[root].ch[1]);
    // 要考虑有相同值的情形，必须要分两次搞，不然有bug
    std::function<void(int)> updateinterval = [&](int x) {
      if (x == 0) return;
      if (tree[tree[x].par].ch[0] == x) {
        if (tree[x].val == tree[tree[x].par].val) r[x] = r[tree[x].par];
      } else {
        if (tree[x].val == tree[tree[x].par].val) l[x] = l[tree[x].par];
      }
      updateinterval(tree[x].ch[0]);
      updateinterval(tree[x].ch[1]);
    };
    updateinterval(tree[root].ch[0]);
    updateinterval(tree[root].ch[1]);
    for (int i = 1; i <= n; ++i) {
      std::cout << l[i] << " " << r[i] << std::endl;
    }
  }
  return 0;
}

洛谷 T126268 「SWTR-05」Subsequence 有一个典型的应用

最小生成树 prim 算法

任取一个节点，然后开始找相邻边中边最小的节点加入，然后继续。百度百科里的图解一看就懂，怎么明确证明正确性呢？（在保证连通的前提下每次删除图中最大的边，不会影响最终结果，而我们每步得到的是当前节点构成的子图的最小生成树）当然了堆优化常规操作，另外不连通输出 INT64_MAX, 例题：LOJ3366

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
using edge = std::vector<std::vector<std::pair<int, int>>>;
LL Prim(const edge &e) {
  LL r = 0;
  int n = e.size(), cnt = 0;
  std::priority_queue<std::pair<int, int>> Q;
  std::vector<int> vis(n);
  Q.push({0, 0});
  while (!Q.empty()) {
    auto [w, u] = Q.top();
    Q.pop();
    if (vis[u]) continue;
    ++cnt;
    r -= w;
    vis[u] = 1;
    for (auto [v, c] : e[u]) if (!vis[v]) {
      Q.push({-c, v});
    }
  }
  return cnt == n ? r : INT64_MAX;
}

最小生成树的 kruskal 法

每次选权值最小的边，然后用 DSU 维护，次方法可推广到 有限个乘积图的最小生成树（https://codeforces.com/gym/103098/problem/C）

最小树形图的 \(O(nm)\) 刘朱算法

  1. 对每个点，找入边权值最小的边构成集合。
  2. 如果这些边构成有向环，缩点后进入 1，否则结束，找到了。

例题：LOJ4716

问题变形：如果不指定根节点，那么可以建一个根节点，然后它和所有其它点连特别大的边即可。

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
using Edge = std::tuple<int, int, int>;
LL LiuZhu(std::vector<Edge> e, int n, int rt) { // e 中无自环
  LL ans = 0;
  while (1) {
    // 寻找入边权值最小的边
    std::vector<int> in(n, INT_MAX), pre(n, -1);
    for (auto [u, v, w] : e) if (u != v && in[v] > w) {
      in[v] = w;
      pre[v] = u;
    }
    // 判定是否无解
    for (int i = 0; i < n; ++i) {
      if (i != rt && pre[i] == -1) return -1;
    }
    // 判定是否有环
    int cnt = 0;
    std::vector<int> vis(n, -1), id(n, -1);
    for (int i = 0; i < n; ++i) if (i != rt) {
      ans += in[i];
      int v = i;
      // 注意到可能出现 6 型的路径，所以两个指标很必要
      while (vis[v] != i && id[v] == -1 && v != rt) {
        vis[v] = i;
        v = pre[v];
      }
      if (id[v] == -1 && v != rt) {
        int u = v;
        do {
          id[u] = cnt;
          u = pre[u];
        } while (u != v);
        ++cnt;
      }
    }
    if (cnt == 0) break;
    // 更新节点和边，也可以重开一个 vector，然后 swap 一下
    for (int i = 0; i < n; ++i) if (id[i] == -1) id[i] = cnt++;
    for (auto &[u, v, w] : e) {
      if (id[u] != id[v]) w -= in[v];
      u = id[u];
      v = id[v];
    }
    rt = id[rt];
    n = cnt;
  }
  return ans;
}

最短路

知乎上看到 YYYYLLL 关于 Floyd 算法的解释挺好的，再次记录(稍加修改）

1
2
3
4
DP[k][i][j] 表示只经过 1～k 号节点优化，i 点到 j 点的最短路径长度。
则 DP[k][i][j] = min( DP[k-1][i][j], DP[k-1][i][k]+DP[k-1][k][j] )
= min( DP[k-1][i][j], DP[k][i][k]+DP[k][k][j] )
DP[0][][] 是初始图的邻接矩阵，DP[n][][] 就是最终求得的最短路长度矩阵了

本来一开始是没法做空间优化的， 但是第二个等式， 就保证了可以做空间优化

1
2
3
4
5
6
7
8
9
10
11
const int N = 1003;
LL dp[N][N];
void Floyd(int n) {
  auto cmin = [](auto &x, auto y) {
    if (x > y) x = y;
  };
  for(int k = 0; k != n; ++k)
    for(int i = 0; i != n; ++i)
      for(int j = 0; j != n; ++j)
        cmin(dp[i][j], dp[i][k] + dp[k][j]);
}

Floyd 带路径 --- 未测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
const int N = 1003;
LL dp[N][N], path[N][N];
void Floyd(int n) {
  memset(path, -1, sizeof(path));
  for(int k = 0; k != n; ++k)
    for(int i = 0; i != n; ++i)
      for(int j = 0; j != n; ++j) if (dp[i][j] > dp[i][k] + dp[k][j]) {
        path[i][j] = k;
      }
}
std::vector<int> getPath(int x, int y) {
  if (path[x][y] == -1) {
    if (x == y) return std::vector<int>{x};
    return std::vector<int>{x, y};
  }
  auto left = getPath(x, path[x][y]);
  auto now = getPath(path[x][y], y);
  left.insert(left.end(), now.begin(), now.end());
  return left;
}

Floyd 算法其它用途：

  • 找最小环（至少三个节点）考虑环上最大节点 \(u\)，\(f[u - 1][x][y]\) 和 \((y, u), (u, x)\) 构成最小环（值小于 INF 才是真的有环）
  • 传递闭包：跟最短路完全类似，只是这里加法改成 或运算，可用 bitset 优化成 \(O(\frac{n^3}{w})\)，其中 \(w = 32, 64\)。

堆优化 Dijkstra

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
using edge = std::vector<std::vector<std::pair<int, int>>>;
std::vector<LL> Dijkstra(int s, const edge &e) {
  std::priority_queue<std::pair<LL, int>> Q;
  std::vector<LL> d(e.size(), INT64_MAX);
  d[s] = 0;
  Q.push({0, s});
  while (!Q.empty()) {
    auto [du, u] = Q.top();
    Q.pop();
    if (d[u] != -du) continue;
    for (auto [v, w] : e[u]) if (d[v] > d[u] + w) {
      d[v] = d[u] + w;
      Q.emplace(-d[v], v);
    }
  }
  return d;
}

堆优化 Dijkstra (弃用)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
using edge = std::vector<std::vector<std::pair<int, int>>>;
std::vector<LL> Dijkstra(int s, const edge &e) {
  std::priority_queue<std::pair<LL, int>> h;
  std::vector<LL> dist(e.size(), INT64_MAX);
  std::vector<int> vis(e.size());
  dist[s] = 0;
  h.push({0, s});
  while (!h.empty()) {
    auto [d, u] = h.top();
    h.pop();
    if (vis[u]) continue;
    vis[u] = 1;
    dist[u] = -d;
    for (auto [v, w] : e[u]) h.emplace(d - w, v);
  }
  return dist;
}

Bellman-Ford

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
using edge = std::vector<std::tuple<int, int, int>>;
bool BellmanFord(edge &e, int n, int x = 0) {
  std::vector<int> dist(n + 1, INT_MAX);
  dist[x] = 0;
  for (int i = 0; i <= n; ++i) {
    bool judge = false;
    for (auto [u, v, w] : e) if (dist[u] != INT_MAX) {
      if (dist[v] > dist[u] + w) {
        dist[v] = dist[u] + w;
        judge = true;
      }
    }
    if (!judge) return true;
  }
  return false;
}

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
using edge = std::vector<std::vector<std::pair<int, int>>>;
bool spfa(edge &e, int x = 0) {
  int n = e.size();
  std::queue<int> Q;
  std::vector<int> dist(n, INT_MAX), cnt(n), inQ(n);
  Q.push(x);
  inQ[x] = 1;
  dist[x] = 0;
  ++cnt[x];
  while (!Q.empty()) {
    int u = Q.front();
    Q.pop();
    inQ[u] = 0;
    for (auto [v, w]: e[u]) {
      if (dist[v] > dist[u] + w) {
        dist[v] = dist[u] + w;
        if (!inQ[v]) {
          Q.push(v);
          inQ[v] = 1;
          if (++cnt[v] == n) return false;
        }
      }
    }
  }
  return true;
}

无向图染色问题

2-color

仅用两种颜色给无向图染色，使得相邻节点不同色，每个连通块考虑即可，每个连通块要么是 2，要么是 0（判断依据有无奇圈）

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
const LL M = 998244353;
// 图以 0 开始编号
LL color2(std::vector<std::vector<int>>& e) {
  int n = e.size();
  std::vector<int> val(n);
  auto bfs = [&](int x) {
    std::queue<int> Q;
    Q.push(x);
    val[x] = 1;
    while (!Q.empty()) {
      int u = Q.front();
      Q.pop();
      for (auto v : e[u]) {
        if (val[v]) {
          if (val[v] != -val[u]) return 0;
        } else {
          val[v] = -val[u];
          Q.push(v);
        }
      }
    }
    return 2;
  };
  LL r = 1;
  for (int i = 0; i < n; ++i) if (val[i] == 0) {
    r = r * bfs(i) % M;
    if (r == 0) return 0;
  }
  return r;
}

The Chromatic Polynomial

对于一般的 \(n\)-color 问题对应的 The Chromatic Polynomial 可在书 Combinatorics and Graph Theory 中找到。思想就是破圈和缩点的做法。

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
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
using BINT = boost::multiprecision::cpp_int;

// chromaticPoly of a tree with n node
std::vector<BINT> chromaticPoly(int n) {
  std::vector<BINT> r(n + 1);
  BINT now{n % 2 == 1 ? 1 : -1};
  for (int i = 0; i < n; ++i) {
    r[i + 1] = now;
    now = -now * (n - 1 - i) / (i + 1);
  }
  return r;
}
std::vector<BINT> colorConnect(std::vector<std::set<int>> e) {
  int n = e.size();
  std::vector<bool> v1(n), v2(n);
  auto r = chromaticPoly(n); // 可以先预处理出来
  auto subtract = [](std::vector<BINT> &a, std::vector<BINT> b) {
    for (int i = 0; i != b.size(); ++i) a[i] -= b[i];
  };
  std::queue<int> Q;
  Q.push(0);
  v1[0] = 1;
  auto enow = e;
  while (!Q.empty()) {
    int u = Q.front();
    v2[u] = 1;
    Q.pop();
    for (auto v : e[u]) if (!v2[v]) {
      if (v1[v]) {
        std::vector<std::set<int>> ed;
        std::vector<int> p(n);
        for (int i = 0, now = 0; i < n; ++i) {
          if (i != u && i != v) {
            p[i] = now++;
          } else p[i] = n - 2;
        }
        for (int i = 0; i < n; ++i) if (i != u && i != v) {
          std::set<int> tmp;
          for (auto x : enow[i]) tmp.insert(p[x]);
          ed.emplace_back(tmp);
        }
        enow[u].erase(v);
        enow[v].erase(u);
        std::set<int> tmp;
        for (auto x : enow[u]) tmp.insert(p[x]);
        for (auto x : enow[v]) tmp.insert(p[x]);
        ed.emplace_back(tmp);
        subtract(r, colorConnect(ed));
      } else {
        Q.push(v);
        v1[v] = 1;
      }
    }
    e = enow;
  }
  return r;
}
std::vector<BINT> color(std::vector<std::set<int>> &e) {
  int n = e.size();
  std::vector<bool> vis(n);
  auto connect = [&](int x) {
    std::vector<bool> visc(n);
    std::queue<int> Q;
    Q.push(x);
    visc[x] = 1;
    while (!Q.empty()) {
      int u = Q.front();
      Q.pop();
      for (auto v : e[u]) if (!visc[v]) {
        visc[v] = 1;
        Q.push(v);
      }
    }
    std::vector<int> p(n);
    for (int i = 0, now = 0; i < n; ++i) if (visc[i]) {
      p[i] = now++;
    }
    std::vector<std::set<int>> ec;
    for (int i = 0; i < n; ++i) if (visc[i]) {
      std::set<int> tmp;
      for (auto x : e[i]) tmp.insert(p[x]);
      ec.emplace_back(tmp);
      vis[i] = 1;
    }
    return ec;
  };
  auto mul = [](std::vector<BINT> &a, std::vector<BINT> b) {
    std::vector<BINT> c(a.size() + b.size() - 1);
    for (int i = 0; i != a.size(); ++i) {
      for (int j = 0; j != b.size(); ++j) {
        c[i + j] += a[i] * b[j];
      }
    }
    return c;
  };
  std::vector<BINT> r(1, 1);
  for (int i = 0; i < n; ++i) if (!vis[i]) {
    r = mul(r, colorConnect(connect(i)));
  }
  return r;
}

int main() {
  // freopen("in","r",stdin);
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int cas = 1;
  std::cin >> cas;
  while (cas--) {
    int n, m;
    std::cin >> n >> m;
    std::vector<std::set<int>> e(n);
    while (m--) {
      int u, v;
      std::cin >> u >> v;
      --u; --v;
      e[u].insert(v);
      e[v].insert(u);
    }
    for (auto x : color(e)) std::cout << x << " ";
    std::cout << std::endl;
  }
  return 0;
}

连通性问题

Kosaraju 缩点算法

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
struct Scc {
  int n, nScc;
  std::vector<int> vis, color, order;
  std::vector<std::vector<int>> e, e2;
  Scc(int _n) : n(_n * 2) {
    nScc = 0;
    e.resize(n);
    e2.resize(n);
    vis.resize(n);
    color.resize(n);
  }
  void addEdge(int u, int v) {
    e[u].emplace_back(v);
    e2[v].emplace_back(u);
  }
  void dfs(int u) {
    vis[u] = true;
    for (auto v : e[u]) if (!vis[v]) dfs(v);
    order.emplace_back(u);
  }
  void dfs2(int u) {
    color[u] = nScc;
    for (auto v : e2[u]) if (!color[v]) dfs2(v);
  }
  void Kosaraju() {
    for (int i = 0; i < n; ++i) if (!vis[i]) dfs(i);
    for (auto it = order.rbegin(); it != order.rend(); ++it) if (!color[*it]) {
      ++nScc;
      dfs2(*it);
    }
  }
};

2-SAT

Kosaraju 算法通过两次 dfs，给强连通分量进行染色，染色数就是强联通分量数，最后缩点后得到的就是一个有向无环图(DAG)，如果有相邻（仅取一个）节点在同一个强连通分量中，那么显然不存在解，否则我们取颜色编号大的连通分量（一定有解！）。

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
// n / 2 对 (2i, 2i + 1)，每对选出一个元素，使得无矛盾
struct twoSAT {
  int n, nScc;
  std::vector<int> vis, color, order;
  std::vector<std::vector<int>> e, e2;
  twoSAT(int _n) : n(_n * 2) {
    nScc = 0;
    e.resize(n);
    e2.resize(n);
    vis.resize(n);
    color.resize(n);
  }
  void addEdge(int u, int v) {
    e[u].emplace_back(v);
    e2[v].emplace_back(u);
  }
  void dfs(int u) {
    vis[u] = true;
    for (auto v : e[u]) if (!vis[v]) dfs(v);
    order.emplace_back(u);
  }
  void dfs2(int u) {
    color[u] = nScc;
    for (auto v : e2[u]) if (!color[v]) dfs2(v);
  }
  void Kosaraju() {
    for (int i = 0; i < n; ++i) if (!vis[i]) dfs(i);
    for (auto it = order.rbegin(); it != order.rend(); ++it) if (!color[*it]) {
      ++nScc;
      dfs2(*it);
    }
  }
  std::vector<int> solve() {
    Kosaraju();
    // 选择颜色编号大的强连通分量
    std::vector<int> choose(nScc + 1);
    for (int i = 0; i < n; i += 2) {
      int c1 = color[i], c2 = color[i + 1];
      if (c1 == c2) return std::vector<int>();
      if (choose[c1] || choose[c2]) continue;
      choose[std::max(c1, c2)] = 1;
    }
    std::vector<int> r(n / 2);
    for (int i = 0; i * 2 < n; ++i) r[i] = (choose[color[i * 2]] ? 1 : -1);
    return r;
  }
};

此内容包含 强连通分量，采用其中的 Kosaraju 算法缩点。参考 OI-wiki 和 百度文库。例题 1：答案，例题 2: K-TV Show Game：答案，有些特殊的 2-SAT 可以用奇偶性解决，例如: 1438C

OI-wiki 割点割边讲解

割点（无向图中删除该点使得连通分量数量增多的节点）

首先 dfs 序给出每个节点的编号记作 dfs[i]，再来一个数组 low，表示不经过父节点能够到达的编号最小的点。显然如果至少有一个儿子满足的 low 值不超过它的 dfs 值，那么此节点就是割点（但是根节点除外，根节点始终满足，如果根节点有大于一个真儿子，那么必然是割点）。不难看出这是割点的冲要条件，因此问题就转化成求 dfs 和 low 了。

模板例题：LOJ3388

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
std::vector<int> cutVertex(std::vector<std::vector<int>>& e) {
  int n = e.size(), cnt = 0;
  std::vector<int> dfs(n), low(n), flag(n), r;
  std::function<void(int, int)> Tarjan = [&](int u, int fa) -> void {
    low[u] = dfs[u] = ++cnt;
    int ch = 0;
    for (auto v : e[u]) {
      if (dfs[v] == 0) {
        ++ch;
        Tarjan(v, u);
        low[u] = std::min(low[u], low[v]);
        if (u != fa && low[v] >= dfs[u]) flag[u] = 1;
      } else if (v != fa) {
        low[u] = std::min(low[u], dfs[v]);
      }
    }
    if (u == fa && ch > 1) flag[u] = 1;
  };
  for (int i = 0; i < n; ++i) if (dfs[i] == 0) Tarjan(i, i);
  for (int i = 0; i < n; ++i) if (flag[i]) r.emplace_back(i);
  return r;
}

割边（无向图中删除该边使得连通分量数量增多的边）

与割点处理同理，只是不用特判根节点。注意到做一次 dfs 后，不在 dfs 路径上的边不可能为割边！但是为了处理重边的情况，没办法只能用 vector 版链式前向星存边了。

模板例题：LOJ T103481

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
class CutEdge {
  int n, cnt;
  std::vector<std::vector<int>> g;
  std::vector<int> e, flag, dfs, low;
  void Tarjan(int u, int inEdgeNum) {
    low[u] = dfs[u] = ++cnt;
    for (auto i : g[u]) {
      int v = e[i];
      if (dfs[v] == 0) {
        Tarjan(v, i);
        low[u] = std::min(low[u], low[v]);
        if (low[v] > dfs[u]) flag[i] = flag[i ^ 1] = 1;
      } else if ((i ^ 1) != inEdgeNum) {
        low[u] = std::min(low[u], dfs[v]);
      }
    }
  }
 public:
  CutEdge(int _n) : n(_n), g(_n), dfs(n), low(n), cnt(0) {}
  void addEdge(int u, int v) {
    if (u == v) return;
    g[u].emplace_back(e.size());
    e.emplace_back(v);
    flag.emplace_back(0);
    g[v].emplace_back(e.size());
    e.emplace_back(u);
    flag.emplace_back(0);
  }
  int solve() {
    for (int i = 0; i < n; ++i) if (dfs[i] == 0) Tarjan(i, -1);
    int r = 0;
    for (auto x : flag) r += x;
    return r / 2;
  }
};

图的匹配算法

OI-wiki 上有专题专门讲这个的，分最大匹配和最大权匹配，对于特殊的图（例如二分图）有特殊的算法，例如可以增加源点和汇点转化成网络流问题，用下面 Dinic 算法在 \(O(\sqrt{n} m)\) 解决。

其中一般图的最大匹配可以参考 Min_25 的模板

网络流

有向图 S-T 最大流 Dinic 算法 \(O(n^2 m)\)（对偶问题：S-T 最大流等于 S-T 最小割）

参考资料：OI-wiki 和 最大流算法-ISAP，需要反向边的原因的例子说明，下面代码借鉴于 jiangly。注意代码本质上是支持动态更新的

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
class Dinic {
  int n;
  // e[i] 表示第 i 条边的终点和容量，注意存边的时候 e[i ^ 1] 是 e[i] 的反向边。
  // g[u] 存的是所有以 u 为起点的边，这就很像链式前向星的做法
  std::vector<std::pair<int, int>> e;
  std::vector<std::vector<int>> g;
  std::vector<int> cur, h;
  // h[i] 表示 bfs 从 s 到 i 的距离，如果找到了 t，那么就说明找到了增广路。
  bool bfs(int s, int t) {
    h.assign(n, -1);
    std::queue<int> Q;
    h[s] = 0;
    Q.push(s);
    while (!Q.empty()) {
      int u = Q.front();
      Q.pop();
      for (auto i : g[u]) {
        auto [v, c] = e[i];
        if (c > 0 && h[v] == -1) {
          h[v] = h[u] + 1;
          Q.push(v);
        }
      }
    }
    return h[t] != -1;
  }
  // f 表示从 u 点出发拥有的最大流量，输出的是 u 到 t 的最大流量
  LL dfs(int u, int t, LL f) {
    if (u == t || f == 0) return f;
    LL r = f;
    for (int &i = cur[u]; i < g[u].size(); ++i) {
      int j = g[u][i];
      auto [v, c] = e[j];
      if (c > 0 && h[v] == h[u] + 1) {
        int a = dfs(v, t, std::min(r, LL(c)));
        e[j].second -= a;
        e[j ^ 1].second += a;
        r -= a;
        if (r == 0) return f;
      }
    }
    return f - r;
  }
 public:
  Dinic(int _n) : n(_n), g(n) {}
  void addEdge(int u, int v, int c) {
    if (u == v) return;
    g[u].emplace_back(e.size());
    e.emplace_back(v, c);
    g[v].emplace_back(e.size());
    e.emplace_back(u, 0);
  }
  LL maxFlow(int s, int t) {
    LL r = 0;
    while (bfs(s, t)) {
      cur.assign(n, 0);
      r += dfs(s, t, INT64_MAX);
    }
    return r;
  }
};

使用 unordered_map 直接存边的 Dinic 算法（注意结果是否超 int）

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
class Dinic {
  int n;
  std::vector<std::unordered_map<int, int>> g;
  std::vector<std::unordered_map<int, int>::iterator> cur;
  std::vector<int> h;
  // h[i] 表示 bfs 从 s 到 i 的距离，如果找到了 t，那么就说明找到了增广路。
  bool bfs(int s, int t) {
    h.assign(n, -1);
    std::queue<int> Q;
    h[s] = 0;
    Q.push(s);
    while (!Q.empty()) {
      int u = Q.front();
      Q.pop();
      for (auto [v, c] : g[u]) {
        if (c > 0 && h[v] == -1) {
          h[v] = h[u] + 1;
          Q.push(v);
        }
      }
    }
    return h[t] != -1;
  }
  // f 表示从 u 点出发拥有的最大流量，输出的是 u 到 t 的最大流量
  int dfs(int u, int t, int f) {
    if (u == t || f == 0) return f;
    int r = f;
    for (auto &it = cur[u]; it != g[u].end(); ++it) {
      int v = it->first;
      if (it->second > 0 && h[v] == h[u] + 1) {
        int a = dfs(v, t, std::min(r, it->second));
        it->second -= a;
        g[v][u] += a;
        r -= a;
        if (r == 0) return f;
      }
    }
    return f - r;
  }
 public:
  Dinic(int _n) : n(_n), g(n), cur(n) {}
  void addEdge(int u, int v, int c) {
    // 注意这里一定要这样！
    if (u == v) return;
    g[u][v] += c;
    g[v][u] += 0;
  }
  int maxFlow(int s, int t) {
    int r = 0;
    while (bfs(s, t)) {
      for (int i = 0; i < n; ++i) cur[i] = g[i].begin();
      r += dfs(s, t, INT_MAX);
    }
    return r;
  }
};

有向图 S-T 最大流 ISAP 算法 (弃用)

核心就是一句话，Dinic 算法中，每一轮需要进行一次 BFS，可以被优化，并且还有许多细节上的优化。

折腾了半天发现并没有比 Dinic 快，本质原因是计算 dfs 完之后更新 d，按照上面的做法会极大的增加 aug(s, INT_MAX) 次数。但是确实比 直接更新 d 更快（可能时因为直接更新高度代码会写的很绕，因为可能变换的高度不止自己一个，父节点的高度也可能要更新），而在下面 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
// 结合 https://www.cnblogs.com/owenyu/p/6852664.html 在实现上进行了相应的修改
class ISAP {
  int n, s, t;
  // e[i] 表示第 i 条边的终点和容量，注意存边的时候 e[i ^ 1] 是 e[i] 的反向边。
  // g[u] 存的是所有以 u 为起点的边，这就很像链式前向星的做法
  std::vector<std::pair<int, int>> e;
  std::vector<std::vector<int>> g;
  // cur[u] 表示以 u 为起点当前没被增广过的边
  std::vector<int> cur, d, gap;
  // d[u] 表示残余网络中 从 u 到 t 的最短距离，注意到可以把 d[u] 理解成连续变化的（否则很难正确的更新 d)。
  // gap[x] 表示 d[u] = x 的节点个数, 用于优化
  void init(int _s, int _t) {
    s = _s;
    t = _t;
    d.assign(n, n);
    std::queue<int> Q;
    d[t] = 0;
    Q.push(t);
    while (!Q.empty()) {
      int u = Q.front();
      Q.pop();
      for (auto i : g[u]) {
        int v = e[i].first, c = e[i ^ 1].second;
        if (c > 0 && d[v] == n) {
          d[v] = d[u] + 1;
          Q.push(v);
        }
      }
    }
    gap.assign(n + 2, 0);
    for (auto x : d) ++gap[x];
    cur.assign(n, 0);
  }
  // 从 u 开始到汇点 t 不超过 f 的最大流，如果取到了 f 说明后面还有增广的可能
  LL aug(int u, LL f) {
    if (u == t) return f;
    LL r = f;
    for (int &i = cur[u]; i < int(g[u].size()); ++i) {
      int j = g[u][i];
      auto [v, c] = e[j];
      if (c > 0 && d[u] == d[v] + 1) {
        int a = aug(v, std::min(r, LL(c)));
        e[j].second -= a;
        e[j ^ 1].second += a;
        r -= a;
        if (r == 0) return f;
      }
    }
    cur[u] = 0;
    if (--gap[d[u]] == 0) d[s] = n;
    ++gap[++d[u]];
    return f - r;
  }
 public:
  ISAP(int _n) : n(_n), g(_n) {}
  void addEdge(int u, int v, int c) {
    if (u == v) return;
    g[u].emplace_back(e.size());
    e.emplace_back(v, c);
    g[v].emplace_back(e.size());
    e.emplace_back(u, 0);
  }
  LL maxFlow(int _s, int _t) {
    init(_s, _t);
    LL r = 0;
    while (d[s] < n) r += aug(s, INT64_MAX);
    return r;
  }
};

有向图 S-T 最大流的最高标号预流推进算法（HLPP） \(O(n^2 \sqrt{m})\) 算法

1988 年 Tarjan, Goldberg 提出次方法，1989 年 Joseph Cheriyan, Kurt Mehlhorn 证明了该方法时间复杂度为 \(O(n^2 \sqrt{m})\)，直接看 OI-wiki 最后一张图（下载下来放大）还是很好理解的，Push-Relabel 那段没讲清楚，跳过的看就行，再结合 cnblog 理解一下优化（不要看代码）就掌握了。然后自己写代码即可。

个人理解其实此算法 ISAP 的优化，Dinic 和 ISAP 都要递归找可行流，但是此算法，先给了再说，多了的再取出来即可，这样不用递归了。

模板例题：LibreOJ-127，跑的太慢，有待提升。

注意到每次推流的时候，当前节点时有水的（且高度小于 n 的，高度为 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
85
86
class HLPP {
  int n;
  // e[i] 表示第 i 条边的终点和容量，注意存边的时候 e[i ^ 1] 是 e[i] 的反向边。
  // g[u] 存的是所有以 u 为起点的边，这就很像链式前向星的做法
  std::vector<std::pair<int, int>> e;
  std::vector<std::vector<int>> g;
  std::vector<int> h;
  std::vector<LL> ex;
  void addFlow(int i, int a) {
    ex[e[i ^ 1].first] -= a;
    ex[e[i].first] += a;
    e[i].second -= a;
    e[i ^ 1].second += a;
  };
  // 首先初始化 u 到 t 的距离得到 d[u]
  bool init(int s, int t) {
    std::queue<int> Q;
    Q.push(t);
    h[t] = 0;
    while (!Q.empty()) {
      int u = Q.front();
      Q.pop();
      for (auto i : g[u]) {
        int v = e[i].first;
        if (e[i ^ 1].second > 0 && h[v] == n) {
          h[v] = h[u] + 1;
          Q.push(v);
        }
      }
    }
    return h[t] == n;
  }
 public:
  HLPP(int _n) : n(_n), ex(n), h(n, n), g(n) {}
  void addEdge(int u, int v, int c) {
    if (u == v) return;
    g[u].emplace_back(e.size());
    e.emplace_back(v, c);
    g[v].emplace_back(e.size());
    e.emplace_back(u, 0);
  }
  LL maxFlow(int s, int t) {
    if (init(s, t)) return 0;
    std::vector<int> gap(n + 1, 0), vis(n);
    for (auto x : h) ++gap[x];
    std::priority_queue<std::pair<int, int>> pq;
    // push 之后 ex[u] 还大于 0 就说明当前超载了，需要提升高度
    auto push = [&](int u) -> bool {
      if (ex[u] == 0 || h[u] == n) return false;
      for (auto i : g[u]) {
        auto [v, c] = e[i];
        // 注意 push(s) 的时候不用管高度的问题
        if (c == 0 || (h[u] != h[v] + 1 && u != s)) continue;
        int a = std::min(ex[u], LL(c));
        addFlow(i, a);
        if (!vis[v]) {
          pq.push({h[v], v});
          vis[v] = 1;
        }
        if (ex[u] == 0) return false;
      }
      return true;
    };
    ex[s] = INT64_MAX;
    push(s);
    h[s] = n;
    vis[s] = vis[t] = 1; // 起点和终点不会丢进队列中
    while (!pq.empty()) {
      int u = pq.top().second;
      pq.pop();
      vis[u] = 0;
      while (push(u)) {
        if (--gap[h[u]] == 0) {
          for (int i = 0; i < n; ++i) if (h[i] > h[u]) h[i] = n;
        }
        h[u] = n - 1;
        for (auto i : g[u]) {
          auto [v, c] = e[i];
          if (c > 0 && h[u] > h[v]) h[u] = h[v];
        }
        ++gap[++h[u]];
      }
    }
    return ex[t];
  }
};

无向图全局最小割 Stoer-Wagner 算法

无向图的 S-T 最小割可以通过 S-T 最大流来做（在 addEdge(u, v, c) 中两个边的权值都是 c 即可！）。 对任意给定的 S 和 T，全局最小割必然是 S-T 最小割或者 S-T 结合成一个节点后得到新图的最小割。Stoer-Wagner 的论文给了一种简单的方式给出某两个点的 S-T 最小割的办法，那么这个最小割的答案存下来，之后再合并这两个点再继续搞即可。而这个方式叫做 cut-of-the-phase，具体说就是，任取一个点，然后每次往这个点中丢 most tightly connected 点，论文中证明了这种方式得到的图，每一步都是最后两个节点的当前图最小割，所以所有点丢进来之后，最后两个节点的割就是原图的这个两个点的最小割。（直接图原论文很好理解，而且有例子说明）

例题：LOJ5632

无向图全局最小割 Stoer-Wagner 算法，邻接矩阵 \(O(n^3)\) 实现

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
// 做完 minCut 之后原图就毁了
class StoerWagner {
  int n;
  std::vector<std::vector<int>> g;
  std::vector<int> del;
  void merge(int s, int t) {
    del[s] = 1;
    for (int i = 0; i < n; ++i) {
      g[i][t] = (g[t][i] += g[s][i]);
    }
  }
 public:
  StoerWagner(int _n) : n(_n), del(n), g(n, std::vector<int>(n)) {}
  void addEdge(int u, int v, int c) {
    if (u == v) return;
    g[u][v] += c;
    g[v][u] += c;
  }
  int minCut() {
    auto f = [&](int cnt, int &s, int &t) -> int {
      std::vector<int> vis(n), d(n);
      auto push = [&](int x){
        vis[x] = 1;
        d[x] = 0;
        for (int i = 0; i < n; ++i) if (!del[i] && !vis[i]) d[i] += g[x][i];
      };
      for (int i = 0; i < cnt; ++i) {
        push(t);
        s = t;
        t = std::max_element(d.begin(), d.end()) - d.begin();
      }
      return d[t];
    };
    int s = 0, t = 0, r = INT_MAX;
    for (int i = n - 1; i > 0; --i) {
      r = std::min(r, f(i, s, t));
      merge(s, t);
    }
    return r == INT_MAX ? 0 : r;
  }
};

无向图全局最小割 Stoer-Wagner 算法，邻接 unorded_map + 优先队列 \(O(nm + n^2 log n)\) 实现（仅稀疏图跑的快, 稠密图还不如 \(O(n^3)\) 的算法）

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
// 做完 minCut 之后原图就毁了
class StoerWagner {
  int n;
  std::vector<int> d, del;
  std::unordered_map<int, std::unordered_map<int, int>> g;
  void merge(int &s, int &t) {
    if (g[s].size() > g[t].size()) std::swap(s, t);
    for (auto [x, c] : g[s]) {
      g[x][t] = (g[t][x] += c);
      g[x].erase(s);
    }
    g.erase(s);
    g[t].erase(t);
  }
 public:
  StoerWagner(int _n) : n(_n), d(n), del(n) {}
  void addEdge(int u, int v, int c) {
    if (u == v) return;
    g[u][v] += c;
    g[v][u] += c;
  }
  int minCut() {
    auto f = [&](int &s, int &t) -> int {
      std::priority_queue<std::pair<int, int>> Q;
      std::fill(d.begin(), d.end(), 0);
      std::fill(del.begin(), del.end(), 0);
      auto push = [&](int x){
        for (auto [i, c] : g[x]) if (!del[i]) {
          Q.push({d[i] += c, i});
        }
        del[x] = 1;
      };
      for (int i = 0; i < n; ++i) {
        push(t);
        s = t;
        while (!Q.empty()) {
          t = Q.top().second;
          if (!del[t]) break;
          Q.pop();
        }
      }
      return d[t];
    };
    int s = 0, t = 0, r = INT_MAX;
    while(--n) {
      r = std::min(r, f(s, t));
      merge(s, t);
    }
    return r == INT_MAX ? 0 : r;
  }
};

无向图全局最小割 Stoer-Wagner 算法，邻接表 + 优先队列 \(O(nm + n^2 log n)\) 实现（仅稀疏图跑的快, 稠密图还不如 \(O(n^3)\) 的算法还是 TLE 属实可惜）

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
using Edge = std::tuple<int, int, int>;
LL StoerWagner(std::vector<Edge> e, int n) {
  auto f = [&]() -> std::tuple<int, int, int> {
    std::priority_queue<std::pair<int, int>> Q;
    std::vector<std::vector<std::pair<int, int>>> in(n);
    for (auto [u, v, w] : e) if (u != v) in[v].emplace_back(u, w);
    std::vector<int> del(n), d(n);
    auto push = [&](int x){
      for (auto [i, c] : in[x]) if (!del[i]) {
        Q.push({d[i] += c, i});
      }
      del[x] = 1;
    };
    int s, t = 0;
    for (int i = 1; i < n; ++i) {
      push(t);
      s = t;
      while (1) {
        if (Q.empty()) {
          for (int i = 0; i < n; ++i) if (!del[i]) Q.push({d[i], i});
        }
        t = Q.top().second;
        Q.pop();
        if (!del[t]) break;
      }
    }
    return {d[t], s, t};
  };
  int s = 0, t = 0, r = INT_MAX;
  while(n > 1 && r > 0) {
    auto [dt, s, t] = f();
    r = std::min(r, dt);
    std::vector<int> id(n);
    int cnt = -1;
    for (int i = 0; i < n; ++i) if (i != s && i != t) id[i] = ++cnt;
    id[s] = id[t] = ++cnt;
    for (auto &[u, v, w] : e) {
      u = id[u];
      v = id[v];
    }
    --n;
  }
  return r == INT_MAX ? 0 : r;
}

最小费用最大流

在最大流的前提下，追求费用最小。一般通用的做法：每次找一条费用最小的可行流。 反向边的费用是原边的相反数，这样就会出现负边，但是因此初始反向边容量为 0，所以初始情况可以理解为图中没有负边。从源点到汇点的费用必然是非负的（因为我们每次走最小费用，所以每次的费用都是非降的，而初始没有负边。）当然这并不代表途中没有经过负边。至于为什么可以用 Dijkstra，很多博客都有介绍。下面代码中 h 为真实的距离，注意到 h[s]始终为 0，对于同一个点，每次的真实距离不减，它将作为下一次求最短路的势。这种思想也称为 Johnson 最短路径算法算法。可以 \(O(n m \log m)\) 解决全源最短路问题。

我们这样再看一次：每次我们找一条最短路径，取流了之后，相当于给这条路径加了反向边，其它的都没有变化，如果我们把当前距离当作势，那么加的这些反向边，其实都可以看作加入了长度为 0 的边。那么我们一直这样搞，就相当于一直没有加入负边！搞定。

由于一般费用最小的路径只有一条，所以我们不妨在求最小费用的时候把前缀边找到，这样就可以直接求路径的最大流了。

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
class Flow {
  inline static const int INF = 1e9;
  int n;
  // e[i] 表示第 i 条边的终点和容量，注意存边的时候 e[i ^ 1] 是 e[i] 的反向边。
  // g[u] 存的是所有以 u 为起点的边，这就很像链式前向星的做法
  std::vector<std::tuple<int, int, int>> e;
  std::vector<std::vector<int>> g;
  std::vector<int> h, path;
  // h[i] 表示 从 s 到 i 的距离，如果找到了 t，那么就说明找到了增广路，作为下一次求距离的势。
  // path[v] 表示从 s 到 v 的最短路中，path[v] 的终点指向 v
  bool Dijkstra(int s, int t) {
    std::priority_queue<std::pair<int, int>> Q;
    std::fill(path.begin(), path.end(), -1);
    std::vector<int> d(n, INF);
    d[s] = 0;
    Q.push({0, s});
    while (!Q.empty()) {
      auto [du, u] = Q.top();
      Q.pop();
      if (d[u] != -du) continue;
      for (auto i : g[u]) {
        auto [v, c, w] = e[i];
        w += h[u] - h[v];
        if (c > 0 && d[v] > d[u] + w) {
          d[v] = d[u] + w;
          path[v] = i;
          Q.push({-d[v], v});
        }
      }
    }
    for (int i = 0; i < n; ++i) {
      if ((h[i] += d[i]) > INF) h[i] = INF;
    }
    return h[t] != INF;
  }
 public:
  Flow(int _n) : n(_n), h(n), path(n), g(n) {}
  void addEdge(int u, int v, int c, int w) {
    if (u == v) return;
    g[u].emplace_back(e.size());
    e.emplace_back(v, c, w);
    g[v].emplace_back(e.size());
    e.emplace_back(u, 0, -w);
  }
  std::pair<LL, LL> maxFlow(int s, int t) {
    LL flow = 0, cost = 0;
    while (Dijkstra(s, t)) {
      int f = INT_MAX, now = t;
      std::vector<int> r;
      while (now != s) {
        r.emplace_back(path[now]);
        f = std::min(f, std::get<1>(e[path[now]]));
        now = std::get<0>(e[path[now] ^ 1]);
      }
      for (auto i : r) {
        std::get<1>(e[i]) -= f;
        std::get<1>(e[i ^ 1]) += f;
      }
      flow += f;
      cost += LL(f) * h[t];
    }
    return {flow, cost};
  }
};

上下界网络流

无源汇上下界可行流

首先每条边先满足下界，那么对应两个节点的入流都要改变，那么为了让每个节点平衡，我们可以起源点和汇点。比如入流多了，那我们可以把它从源点给它连这么多流的边，求最大流的时候，自然就会有出的跟他中和。

这样只需在差网络中求一下最大流得到的必然是可行流

有源汇上下界可行流

从汇点到源点建一个 下界为 0，上界无穷大的边，就变成了无源汇情形

有源汇上下界最大流

求完可行流之后，再根据原始的源汇求一次最大流即可。

有源汇上下界最小流

求完可行流之后，再根据原始的源汇（源汇互换）求一次最大流即可。

（有/无）源汇上下界最小费流

附加边费用为 0，然后按照最小费用最大流跑一次就可以了。

（有/无）源汇上下界最小费用最大流

附加边费用为 0，然后按照最小费用最大流跑一次就可以了。然后再根据原始的源汇跑一次最大流即可。