Siyuan 的博客 - 网络流
type: channel
link: https://blog.siyuanw.cn/tag/Network-Flow/
items: 「2019 Multi-University Training Contest 2」Harmonious Army
items: 「AHOI 2014」支线剧情
items: 「算法笔记」网络流 - 上下界网络流
items: 「UOJ 336」无限之环
items: 「Codeforces 280D」K-Maximum Subsequence Sum
items: 「算法笔记」网络流 - 费用流
items: 「BJOI 2006」狼抓兔子
items: 「算法笔记」网络流 - 最小割
items: 「算法笔记」二分图多重匹配
items: 「算法笔记」网络流 - 最大流

「2019 Multi-University Training Contest 2」Harmonious Army
type: item
date: 2019-07-29T19:00:00+08:00
description: 题目链接：HDU 6598在一个军队里有 $n$ 名士兵。每名士兵需要分配一个任务：Mage 或 Warrior。这些士兵中有 $m$ 对士兵有良好的凝聚力。如果这两名士兵都参加 Warrior 任务，军队的效率会增加 $a$；如果这两名士兵都参加 Mage 任务，军队的效率会增加 $c$；否则军队的效率会增加 $b = \frac{a}{4} + \frac{c}{3}$（保证 $4 \mid a, 3 \mid c$）。你需要求出军队效率的最大值。本题有多组数据。数据范围：$1 \le n \le 500$，$0 \le m \le 10 ^ 4$，$1 \le a, b \le 4 \times 10 ^ 6$，$\sum n \le 5 \times 10 ^ 3$，$\sum m \le 5 \times 10 ^ 4$。Solution考虑「网络流」。我们对于点 $u, v$ 建立如下网络图（我才不会告诉你们图片是从官方题解搬来的）：设三种贡献分别为 $A, B, C$，通过最小割的实际意义，我们建立方程：$$ \begin{cases} a + b = A + B \\ c + d = C + B \\ a + d + e = A + C \\ b + c + e = A + C \end{cases} $$解得一组解为：$$ \begin{cases} a = b = \frac{A + B}{2} \\ c = d = \frac{C + B}{2} \\ e = \frac{A + C - 2B}{2} \end{cases} $$直接跑最小割即可。时间复杂度：$\mathcal O(n ^ {2} m)$。Code#include <cstdio> #include <algorithm> #include <queue> const int N = 5e2 + 5, M = 1e4 + 5; const int INF = 0x7f7f7f7f; int n, m, vs[N], vt[N]; template <class Tp, int N, int M, bool opt> struct Network { static const int INF = 0x7f7f7f7f; int n, tot = 1, lnk[N], cur[N], ter[M], nxt[M], dis[N]; Tp cap[M], flow[M]; void clear() { std::fill(lnk + 1, lnk + n + 1, 0); n = 0, tot = 1; } void addEdge(int u, int v, Tp w) { ter[++tot] = v, nxt[tot] = lnk[u], lnk[u] = tot; cap[tot] = w, flow[tot] = 0; } void addArc(int u, int v, Tp w) { addEdge(u, v, w), addEdge(v, u, 0); } #if opt Tp dif[N]; void addArc(int u, int v, Tp l, Tp r) { dif[u] -= l, dif[v] += l, addArc(u, v, r - l); } #endif bool bfs(int s, int t) { std::queue<int> q; std::fill(dis + 1, dis + n + 1, INF); std::copy(lnk + 1, lnk + n + 1, cur + 1); dis[s] = 0, q.push(s); for (; !q.empty(); ) { int u = q.front(); q.pop(); for (int i = lnk[u]; i; i = nxt[i]) { int v = ter[i]; if (cap[i] > flow[i] && dis[v] == INF) { dis[v] = dis[u] + 1, q.push(v); } } } return dis[t] < INF; } Tp dfs(int u, int t, Tp f) { if (u == t) return f; Tp ans = 0; for (int &i = cur[u]; i; i = nxt[i]) { int v = ter[i]; if (cap[i] > flow[i] && dis[v] == dis[u] + 1) { Tp x = dfs(v, t, std::min(f, cap[i] - flow[i])); flow[i] += x, …

「AHOI 2014」支线剧情
type: item
date: 2019-04-02T19:00:00+08:00
description: 题目链接：LOJ 2226宅男 JYY 非常喜欢玩 RPG 游戏，比如仙剑，轩辕剑等等。不过 JYY 喜欢的并不是战斗场景，而是类似电视剧一般的充满恩怨情仇的剧情。这些游戏往往都有很多的支线剧情，现在 JYY 想花费最少的时间看完所有的支线剧情。JYY 现在所玩的 RPG 游戏中，一共有 $n$ 个剧情点，由 $1$ 到 $n$ 编号，第 $i$ 个剧情点可以根据 JYY 的不同的选择，而经过不同的支线剧情，前往 $K_i$ 种不同的新的剧情点。当然 $K_i$ 如果为 $0$，则说明 $i$ 号剧情点是游戏的一个结局了。JYY 观看一个支线剧情需要一定的时间。JYY 一开始处在 $1$ 号剧情点，也就是游戏的开始。显然任何一个剧情点都是从 $1$ 号剧情点可达的。此外，随着游戏的进行，剧情是不可逆的。所以游戏保证从任意剧情点出发，都不能再回到这个剧情点。由于 JYY 过度使用修改器，导致游戏的「存档」和「读档」功能损坏了，所以 JYY 要想回到之前的剧情点，唯一的方法就是退出当前游戏，并开始新的游戏，也就是回到 $1$ 号剧情点。JYY 可以在任何时刻退出游戏并重新开始。不断开始新的游戏重复观看已经看过的剧情很是痛苦，JYY 希望花费最少的时间，看完所有不同的支线剧情。数据范围：$1 \le n \le 300$，$0 \le K_i \le 50$，$\sum_{i = 1} ^ n K_i \le 5000$。Solution刚看到题目可能会想到最小链覆盖，但是发现每条链必须从起点出发，并且边有权值，我们可以尝试往网络流的方向思考。每条边至少经过 $1$ 次可以转化为这条边的流量下界为 $1$，上界为 $\infty$，费用为花费时间。直接套用有源汇有上下界费用流求解即可。时间复杂度：$\mathcal O(n\sum K_i f)$。Code#include <cstdio> #include <cstring> #include <algorithm> #include <queue> const int N = 3e2 + 5, M = 2e4 + 5; const int INF = 0x7f7f7f7f; int n, m, deg[N], dis[N]; int tot = 1, lnk[N], cur[N], ter[M], nxt[M], cap[M], cost[M]; bool vis[N]; void add(int u, int v, int w, int c) { ter[++tot] = v, nxt[tot] = lnk[u], lnk[u] = tot, cap[tot] = w, cost[tot] = c; } void addEdge(int u, int v, int w, int c) { add(u, v, w, c), add(v, u, 0, -c); } bool spfa(int s, int t) { memset(dis, 0x7f, sizeof(dis)); memcpy(cur, lnk, sizeof(lnk)); std::queue<int> q; q.push(s), dis[s] = 0, vis[s] = true; while (!q.empty()) { int u = q.front(); q.pop(), vis[u] = false; for (int i = lnk[u]; i; i = nxt[i]) { int v = ter[i]; if (cap[i] && dis[v] > dis[u] + cost[i]) { dis[v] = dis[u] + cost[i]; if (!vis[v]) q.push(v), vis[v] = true; } } } return dis[t] < INF; } int dfs(int u, int t, int flow) { if (u == t) return flow; vis[u] = true; int ans = 0; for (int &i = cur[u]; i; i = nxt[i]) { int v = ter[i]; if (cap[i] && !vis[v] && dis[v] == dis[u] + cost[i]) { int x = dfs(v, t, std::min(cap[i], flow)); if (!x) continue; cap[i] -= x, cap[i ^ 1] += x, flow -= x, ans += x; if (!flow) break; } } vis[u] = false; return ans; } std::pair…

「算法笔记」网络流 - 上下界网络流
type: item
date: 2019-04-02T18:00:00+08:00
description: [scode type="green"]所谓上下界网络流，就是在网络图中给每条边指定一个流量下界和上界。这类网络流问题有很多模型，需要根据不同性质进行转化。[/scode]网络流系列文章最大流最小割费用流上下界网络流概述本文中，我们用 $(u, v, l, r)$ 来表示边 $(u, v)$ 的容量的下界为 $l$、上界为 $r$；用 $s', t'$ 表示虚源点和虚汇点；用 $s, t$ 表示源点和汇点。我们将上下界网络流问题分成若干类，下文将具体展开讲述。无源汇可行流思路首先我们需要增加虚源点和虚汇点，然后考虑如何建图。对于边 $(u, v, l, r)$，流量 $l$ 是必须流过的，流量 $r - l$ 是自由流量。换言之，如果我们强制从 $u$ 流出 $l$ 的流量，强制向 $v$ 流入 $l$ 的流量，那么就可以转化为容量为 $r - l$ 的一般网络流问题了。这个问题看似比较难处理，那么我们先考虑一个判定性问题：这种网络图是否有可行流？通过上述分析可以将这个问题转化为：是否可以从 $u$ 流出 $l$ 的流量，向 $v$ 流入 $l$ 的流量？现在这个问题已经比较容易了，我们将边 $(u, v, l, r)$ 拆成如下 $3$ 条边：边 $(s', v)​$，容量为 $l​$，也就是强制向 $v​$ 流入 $l​$ 的流量。边 $(u, t')$，容量为 $l$，也就是强制从 $u$ 流出 $l$ 的流量。边 $(u, v)$，容量为 $r - l$，也就是自由流量。下文将前 $2$ 条边称为附加边。接下来在这种图上跑最大流。判断是否可行的方法为：附加边是否满流；换言之就是最大流是否为所有边的下界容量之和。如果有解，我们只需要将每条边的流量加上下界容量就是一组可行流了。代码#include <cstdio> #include <cstring> #include <algorithm> #include <queue> const int N = 1e5 + 5, M = 4e5 + 5; const int INF = 0x7f7f7f7f; int n, m, low[M], deg[N], dis[N]; int tot = 1, lnk[N], cur[N], ter[M], nxt[M], cap[M]; void add(int u, int v, int w) { ter[++tot] = v, nxt[tot] = lnk[u], lnk[u] = tot, cap[tot] = w; } void addEdge(int u, int v, int w) { add(u, v, w), add(v, u, 0); } bool bfs(int s, int t) { memset(dis, -1, sizeof(dis)); memcpy(cur, lnk, sizeof(lnk)); std::queue<int> q; q.push(s), dis[s] = 0; while (!q.empty()) { int u = q.front(); q.pop(); for (int i = lnk[u]; i; i = nxt[i]) { int v = ter[i]; if (cap[i] && dis[v] < 0) { q.push(v), dis[v] = dis[u] + 1; } } } return dis[t] >= 0; } int dfs(int u, int t, int flow) { if (u == t) return flow; int ans = 0; for (int &i = cur[u]; i; i = nxt[i]) { int v = ter[i]; if (cap[i] && dis[v] == dis[u] + 1) { int x = dfs(v, t, std::min(cap[i], flow)); if (!x) continue; cap[i] -= x, cap[i ^ 1] += x, flow -= x, ans += x; if (!flow) return ans; } } dis[u] = -1; return ans; } int dinic(int s, int t) { int ans = 0; while (bfs(s, t)) { int x; while ((x = dfs(s, t, INF))) ans += x; } return ans; } int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= m; i++) { int u, v, l, r; sc…

「UOJ 336」无限之环
type: item
date: 2019-03-31T12:00:00+08:00
description: 题目链接：UOJ 336曾经有一款流行的游戏，叫做Infinity Loop，先来简单的介绍一下这个游戏：游戏在一个 $n \times m$ 的网格状棋盘上进行，其中有些小方格中会有水管，水管可能在方格某些方向的边界的中点有接口，所有水管的粗细都相同，所以如果两个相邻方格的公共边界的中点都有接头，那么可以看作这两个接头互相连接。水管有以下 $15$ 种形状：游戏开始时，棋盘中水管可能存在漏水的地方。形式化地：如果存在某个接头，没有和其它接头相连接，那么它就是一个漏水的地方。玩家可以进行一种操作：选定一个含有非直线型水管的方格，将其中的水管绕方格中心顺时针或逆时针旋转 $90$ 度。直线型水管是指左图里中间一行的两种水管。现给出一个初始局面，请问最少进行多少次操作可以使棋盘上不存在漏水的地方。如果无法达成目标，输出 $-1$。数据范围：$1 \le n \times m \le 2000$。Solution借鉴一下 Tiger0132 博客中的一句话：判断网络流的一个办法：网格图 / 棋盘 / 有规律的图案有一些与暴力算法无关的奇怪性质这道题：是棋盘；直管不能翻转。鉴定完毕。于是我们考虑如何建模。由于有旋转操作，于是我们把每个格子拆成 $4$ 个点，分别代表上下左右四个方向。又观察到是否漏水只和相邻两个格子有关，于是我们对棋盘进行黑白染色。黑点连向源点，白点连向汇点（注意这里的点是水管有接口的方向上的所有点），容量为 $1$，费用为 $0$。我们把合法的接头数量看做是流量，将旋转次数看做是费用。如果最大流量等于要求的接头数量，那么最小费用就是最少的交换次数。对于每个格子​，我们用 ​$\text{U}, \text{R}, \text{D}, \text{L}$ 表示其拆点后的上、右、下、左四个点。对于格子 $(i, j)$，我们将 $\text{U}_{i, j}, \text{R}_{i, j}, \text{D}_{i, j}, \text{L}_{i, j}$ 分别和 $\text{D}_{i - 1, j}, \text{L}_{i, j + 1}, \text{U}_{i + 1, j}, \text{R}_{i, j - 1}$ 连一条容量为 $1$，费用为 $0$ 的边（注意连边方向是从源点向汇点）。对于所有的水管形态，我们将它们分为本质不同的几种：直管、十字直管不能旋转，因此不需要考虑旋转导致的连边；十字旋转不会产生任何影响，因此也不需要额外连边。单叉、直角、三叉考虑一次旋转造成的影响：获得一个新的方向上的接口，同时失去一个方向上的接口。那么我们从被删除的方向上的点向获得的方向上的点连一条容量为 $1$，费用为旋转次数的边。正确性考虑证明这样连边的正确性。每个点向源汇点连边的容量均为 $1$，意味着只能旋转一次、并且代表一个接口数量。一个部分的点只会和另一个部分的唯一一个点匹配，正确性得证。建好图之后直接跑最小费用最大流即可。时间复杂度：$\mathcal O(n ^ 3 m ^ 3)$。Code#include <cstdio> #include <cstring> #include <algorithm> #include <queue> #define U k + 0 #define R k + 1 #define D k + 2 #define L k + 3 #define E(x, y, c) addEdge(x, y, 1, c, opt) const int N = 8e3 + 5, M = 1.5e5 + 5; const int INF = 0x3f3f3f3f; int n, m, maxFlow, minCost, tot = 1, lnk[N], cur[N], ter[M], nxt[M], cap[M], cost[M], dis[N]; bool vis[N]; void add(int u, int v, int w, int c) { ter[++tot] = v, nxt[tot] = lnk[u], lnk[u] = tot, cap[tot] = w, cost[tot] = c; } void addEdge(int u, int v, int w, int c, bool rev) { if (rev) std::swap(u, v); add(u, v, w, c), add(v, u, 0, -c); } bool spfa(int s, int t) { memset(dis, 0x3f, sizeof(dis)); memcpy(cur, lnk, sizeof(lnk)); std::queue<int> q; q.push(s), dis[s] = 0…

「Codeforces 280D」K-Maximum Subsequence Sum
type: item
date: 2019-03-19T19:00:00+08:00
description: 题目链接：Codeforces 280D你有一个长度为 $n$ 的序列 $a_i$，接下来进行 $m$ 次操作，操作分为如下 $2$ 种：0 i val：将第 $i$ 个数 $a_i$ 修改为 $val$。1 l r k：你需要在序列 $a_l, a_{l + 1}, \cdots, a_r$ 中找出至多 $k$ 个不相交的子序列，使得他们的和最大。形式化地，你需要找出至多 $k$ 对 $(x_1, y_1), (x_2, y_2), \cdots, (x_t, y_t)$（其中 $l\le x_1\le y_1<x_2\le y_2<\cdots<x_t \le y_t\le r$，$0\le t\le k$），使得 $(a_{x_1} + a_{x_1 + 1} + \cdots + a_{y_1}) + (a_{x_2} + a_{x_ 2 + 1} + \cdots + a_{y_2})+\cdots + (a_{x_t} + a_{x_t + 1} + \cdots + a_{y_t})$ 的值最大。特别地，你可以选择 $0$ 个子序列，这时和式等于 $0$。数据范围：$1 \le n, m\le 10 ^ 5$，$\vert a_i, val \vert \le 500$，$1\le k\le 20$，求 $k$ 个子序列和的操作不超过 $10^4$ 个。Solution我们很容易建立起费用流的模型。源点像每个点连流量为 $1$、费用为 $0$ 的边。每个点向下一个点连流量 $1$，费用为 $a_i$ 的边。每个点向汇点连流量为 $1$、费用为 $0$ 的边。可以发现多流一个单位的流量就会多出一个区间。那么问题就变成使用不超过 $k$ 个单位的流量，能够得到的最大费用。但是直接上费用流肯定 $\text{TLE}$，但是注意到每次増广的贡献是一段区间，我们考虑用线段树维护来模拟费用流。我们把増广的过程转化为线段树能处理的问题：每次増广相当于询问整个区间的最大子段和。每次更新反向弧的费用相当于将区间取反。増广 $k$ 次相当于在线段树上进行上述过程 $k$ 次。这样一来我们就可以直接在线段树上操作了！最后考虑一下代码实现问题！由于我们要实现区间最大子段和及其范围、区间取反，因此需要维护的不止左右端点最大值、区间最大答案……对于每个最大值，还需要记录最小值，这样才能实现区间取反的问题。为了使代码难度降低，我们可以定义一个 $\text{struct}$ 记录每个值的 $l,r,val$ 等信息，重载运算符来合并区间。时间复杂度：$\mathcal O(mk\log n)$ 且带有大常数。Code#include <cstdio> #include <algorithm> #define lson p << 1 #define rson p << 1 | 1 const int N = 1e5 + 5; int n, m, A[N]; struct Data { int l, r, val; Data(int _l = 0, int _r = 0, int _val = 0) { l = _l, r = _r, val = _val; } Data operator+(const Data &b) const { return Data(l, b.r, val + b.val); } bool operator<(const Data &b) const { return val < b.val; } }; struct Node { int rev; Data sum, lmx, lmn, rmx, rmn, smx, smn; Node() { rev = 0; sum = lmx = lmn = rmx = rmn = smx = smn = Data(); } void init(int pos, int val) { rev = 0; sum = lmx = lmn = rmx = rmn = smx = smn = Data(pos, pos, val); } void reverse() { rev ^= 1; std::swap(lmx, lmn); std::swap(rmx, rmn); std::swap(smx, smn); sum.val *= -1; lmx.val *= -1, lmn.val *= -1; rmx.val *= -1, rmn.val *= -1; smx.val *= -1, smn.val *= -1; } }; struct Segment { Node a[N << 2]; Node merge(Node x, Node y) { Node ans; ans.sum…

「算法笔记」网络流 - 费用流
type: item
date: 2018-12-27T10:30:00+08:00
description: [scode type="green"]最小费用最大流，指在保证最大流量的同时最小费用。[/scode]网络流系列文章最大流最小割费用流上下界网络流概念费用我们定义一条边的费用 $w(u,v)$ 表示边 $(u,v)$ 上单位流量的费用。也就是说，当边 $(u,v)$ 的流量为 $f(u,v)$ 时，需要花费 $f(u,v)\times w(u,v)$ 的费用。最小费用最大流网络流图中，花费最小的最大流被称为最小费用最大流，这也是接下来我们要研究的对象。求解我们可以在 $\text{Dinic}​$ 算法的基础上进行改进，把 $\text{BFS}​$ 求分层图改为用 $\text{SPFA}​$（由于有负权边，所以不能直接用 $\text{Dijkstra}​$）来求一条单位费用之和最小的路径，也就是把 $w(u,v)​$ 当做边权然后在残量网络上求最短路，当然在 $\text{DFS}​$ 中也要略作修改。这样就可以求得网络流图的最小费用最大流了。如何建反向边？对于一条边 $(u,v,w,c)$（其中 $w$ 和 $c$ 分别为容量和费用），我们建立正向边 $(u,v,w,c)$ 和反向边 $(v,u,0,-c)$（其中 $-c$ 是使得从反向边经过时退回原来的费用）。优化：如果你是“关于 $\text{SPFA}$，它死了”言论的追随者，那么你可以使用 $\text{Primal-Dual}$ 原始对偶算法将 $\text{SPFA}$ 改成 $\text{Dijkstra}$！时间复杂度：可以证明上界为 $\mathcal O(nmf)$，其中 $f$ 表示流量。代码#include <cstdio> #include <cstring> #include <algorithm> #include <queue> const int N = 1e5 + 5, M = 2e5 + 5; const int INF = 0x7f7f7f7f; int n, m, s, t, dis[N]; int tot = 1, lnk[N], cur[N], ter[M], nxt[M], cap[M], cost[M]; bool vis[N]; void add(int u, int v, int w, int c) { ter[++tot] = v, nxt[tot] = lnk[u], lnk[u] = tot, cap[tot] = w, cost[tot] = c; } void addEdge(int u, int v, int w, int c) { add(u, v, w, c), add(v, u, 0, -c); } bool spfa(int s, int t) { memset(dis, 0x7f, sizeof(dis)); memcpy(cur, lnk, sizeof(lnk)); std::queue<int> q; q.push(s), dis[s] = 0, vis[s] = true; while (!q.empty()) { int u = q.front(); q.pop(), vis[u] = false; for (int i = lnk[u]; i; i = nxt[i]) { int v = ter[i]; if (cap[i] && dis[v] > dis[u] + cost[i]) { dis[v] = dis[u] + cost[i]; if (!vis[v]) q.push(v), vis[v] = true; } } } return dis[t] < INF; } int dfs(int u, int t, int flow) { if (u == t) return flow; vis[u] = true; int ans = 0; for (int &i = cur[u]; i; i = nxt[i]) { int v = ter[i]; if (cap[i] && !vis[v] && dis[v] == dis[u] + cost[i]) { int x = dfs(v, t, std::min(cap[i], flow)); if (!x) continue; cap[i] -= x, cap[i ^ 1] += x, flow -= x, ans += x; if (!flow) break; } } vis[u] = false; return ans; } std::pair<int, int> dinic(int s, int t) { int maxFlow = 0, minCost = 0; while (spfa(s, t)) { int x; …

「BJOI 2006」狼抓兔子
type: item
date: 2018-12-15T11:00:00+08:00
description: 题目链接：BZOJ 1001现在小朋友们最喜欢的"喜羊羊与灰太狼"，话说灰太狼抓羊不到，但抓兔子还是比较在行的，而且现在的兔子还比较笨，它们只有两个窝，现在你做为狼王，面对下面这样一个网格的地形：左上角点为 $(1,1)$，右下角点为 $(n,m)$（上图中 $n=3, m=4​$）。有以下三种类型的道路：$(x,y)\longleftrightarrow(x+1,y)$$(x,y)\longleftrightarrow(x,y+1)$$(x,y)\longleftrightarrow(x+1,y+1)$道路上的权值表示这条路上最多能够通过的兔子数，道路是无向的。左上角和右下角为兔子的两个窝，开始时所有的兔子都聚集在左上角 $(1,1)$ 的窝里，现在它们要跑到右下角 $(n,m)$ 的窝中去，狼王开始伏击这些兔子.当然为了保险起见，如果一条道路上最多通过的兔子数为 $k$，狼王需要安排同样数量的 $k$ 只狼，才能完全封锁这条道路，你需要帮助狼王安排一个伏击方案，使得在将兔子一网打尽的前提下，参与的狼的数量要最小。数据范围：$1\le n, m\le 1000$。Solution很显然是一个裸的最小割，对 $(1,1)$ 到 $(n,m)$ 依次编号，然后按照题意建边跑最短路即可 QAQ吐槽：终于做出了 BZOJ 的 1001（大雾当然由于这题的图是一张平面图，所以我们也可以建出对偶图，直接跑最短路，得到的就是原图的最小割。时间复杂度：$\mathcal O((nm)^3)$。Code#include <cstdio> #include <cstring> #include <algorithm> #include <queue> const int N = 1e6 + 5, M = 6e6 + 5; const int INF = 0x3f3f3f3f; int n, m, tot = 1, lnk[N], ter[M], nxt[M], val[M], dep[N], cur[N]; int id(int x, int y) { return (x - 1) * m + y; } void add(int u, int v, int w) { ter[++tot] = v, nxt[tot] = lnk[u], lnk[u] = tot, val[tot] = w; } void addEdge(int u, int v, int w) { add(u, v, w), add(v, u, w); } int bfs(int s, int t) { memset(dep, 0, sizeof(dep)); memcpy(cur, lnk, sizeof(lnk)); std::queue<int> q; q.push(s), dep[s] = 1; while (!q.empty()) { int u = q.front(); q.pop(); for (int i = lnk[u]; i; i = nxt[i]) { int v = ter[i]; if (val[i] && !dep[v]) { q.push(v), dep[v] = dep[u] + 1; } } } return dep[t]; } int dfs(int u, int t, int flow) { if (u == t) return flow; int ans = 0; for (int &i = cur[u]; i && ans < flow; i = nxt[i]) { int v = ter[i]; if (val[i] && dep[v] == dep[u] + 1) { int x = dfs(v, t, std::min(val[i], flow - ans)); if (x) { val[i] -= x, val[i ^ 1] += x, ans += x; } } } if (ans < flow) dep[u] = -1; return ans; } int dinic(int s, int t) { int ans = 0; while (bfs(s, t)) { int x; while ((x = dfs(s, t, INF))) ans += x; } return ans; } int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) { for (int j = 1; j < m; j++) { int x; scanf("%d", &x); addEdge(id(i, j), id(i, j + 1), x); } } for (int i …

「算法笔记」网络流 - 最小割
type: item
date: 2018-12-09T18:30:00+08:00
description: [scode type="green"]最小割，指割去一些边使得源点和汇点不连通的最小花费，有最大流最小割定理。[/scode]网络流系列文章最大流最小割费用流上下界网络流概念割对于一个网络流图 $G=(V,E)$，其割的定义为一种点的划分方式：将所有的点划分为 $S$ 和 $T=V-S$ 两个集合，其中源点 $s\in S$，汇点 $t\in T$。割的容量我们的定义割 $(S,T)$ 的容量 $c(S,T)$ 表示所有从 $S$ 到 $T$ 的边的容量之和，即 $c(S,T)=\sum_{u\in S,v\in T}c(u,v)$。当然我们也可以用 $c(s,t)$ 表示 $c(S,T)$。最小割最小割就是求得一个割 $(S,T)$ 使得割的容量 $c(S,T)$ 最小。证明最大流最小割定理定理：$f(s,t)_{\max}=c(s,t)_{\min}$对于任意一个可行流 $f(s,t)$ 的割 $(S,T)$，我们可以得到：$$ f(s,t)=S\ \text{出边的总流量}-S\ \text{入边的总流量}\le S\ \text{出边的总流量}=c(s,t) $$如果我们求出了最大流 $f$，那么残余网络中一定不存在 $s$ 到 $t$ 的増广路经，也就是 $S$ 的出边一定是满流，$S$ 的入边一定是零流，于是有：$$ f(s,t)=S\ \text{出边的总流量}-S\ \text{入边的总流量}=S\ \text{出边的总流量}=c(s,t) $$结合前面的不等式，我们可以知道此时 $f$ 已经达到最大。代码最小割通过最大流最小割定理，我们可以直接得到如下代码：#include <cstdio> #include <cstring> #include <algorithm> #include <queue> const int N = 1e4 + 5, M = 2e5 + 5; const int INF = 0x3f3f3f3f; int n, m, s, t, tot = 1, lnk[N], ter[M], nxt[M], val[M], dep[N], cur[N]; void add(int u, int v, int w) { ter[++tot] = v, nxt[tot] = lnk[u], lnk[u] = tot, val[tot] = w; } void addedge(int u, int v, int w) { add(u, v, w), add(v, u, 0); } int bfs(int s, int t) { memset(dep, 0, sizeof(dep)); memcpy(cur, lnk, sizeof(lnk)); std::queue<int> q; q.push(s), dep[s] = 1; while (!q.empty()) { int u = q.front(); q.pop(); for (int i = lnk[u]; i; i = nxt[i]) { int v = ter[i]; if (val[i] && !dep[v]) { q.push(v), dep[v] = dep[u] + 1; } } } return dep[t]; } int dfs(int u, int t, int flow) { if (u == t) return flow; int ans = 0; for (int &i = cur[u]; i && ans < flow; i = nxt[i]) { int v = ter[i]; if (val[i] && dep[v] == dep[u] + 1) { int x = dfs(v, t, std::min(val[i], flow - ans)); if (x) { val[i] -= x, val[i ^ 1] += x, ans += x; } } } if (ans < flow) dep[u] = -1; return ans; } int dinic(int s, int t) { int ans = 0; while (bfs(s, t)) { int x; while ((x = dfs(s, t, INF))) ans += x; } return ans; } int main() { scanf("%d%d%d%d", &n, &m, &s, &t); for (int i = 1; i <= m; i++) { int u, v, w; scanf("%d%d%d", &u, &v, &w); addedge(u, v, w); } printf("%d\n", dinic(s, t));…

「算法笔记」二分图多重匹配
type: item
date: 2018-12-09T13:00:00+08:00
description: [scode type="green"]在二分图最大匹配问题中，每个点最多只能和一条匹配边相关联。但是二分图多重匹配中，每个点可以多次匹配但是有匹配上限。[/scode]例题Description学校运动会即将开始，运动会有 $m$ 个项目，第 $i$ 个项目每个班必须派出 $p_i$ 名学生参加。班级里有 $n$ 名学生，第 $i$ 名学生最多参加 $a_i$ 个项目，并且他给出了他擅长的 $b_i​$ 个项目的编号。求是否有一个合适的安排满足条件。数据范围：$1\le n,m\le 100$。Solution我们把 $n$ 名学生和 $m$ 个项目看作是二分图的 $A,B$ 两部。那么每个学生向他擅长的项目连边。这就是二分图匹配的一般思想。由于有 $a_i$ 和 $p_i$ 的限制，我们要求 $A$ 部的点关联的边不能超过 $a_i$ 个，那么我们需要一个方法来限制这个量在 $[0,a_i]$ 之间。这样一来，有没有感觉特别想网络流中的容量？于是我们可以对二分图进行扩展，建立源点 $s$ 和汇点 $t$，在 $s$ 和 $A$ 部的第 $i$ 个点之间连一条容量为 $a_i$ 的边，在 $A$ 部和 $B$ 部之间相连的边的容量为 $1$，从 $B$ 部的第 $i$ 个点向 $t$ 连一条容量为 $p_i$ 的边。这个连边方式的正确性显然。我们对这张图跑最大流，然后分析一下各个边的含义：边 $(s,A_i)$ 表示学生 $A_i$ 参加的项目数量。边 $(A_i,B_j)$ 表示 $A_i$ 是否参加了 $B_j$ 项目。边 $(B_i,t)$ 表示项目 $B_i$ 的参加人数。所以是否有合适方案，我们只要判断是否所有的边 $(B_i,t)$ 都满流即可！时间复杂度：$\mathcal O((n+m)\cdot(nm)^2)$。Code#include <cstdio> #include <cstring> #include <algorithm> #include <queue> const int N = 205, M = 5e4 + 5; const int INF = 0x3f3f3f3f; int n, m, tot = 1, lnk[N], ter[M], nxt[M], val[M], dep[N], cur[N]; int id(int p, int x) { return p == 1 ? x : n + x; } void add(int u, int v, int w) { ter[++tot] = v, nxt[tot] = lnk[u], lnk[u] = tot, val[tot] = w; } void addedge(int u, int v, int w) { add(u, v, w), add(v, u, 0); } int bfs(int s, int t) { memset(dep, 0, sizeof(dep)); memcpy(cur, lnk, sizeof(lnk)); std::queue<int> q; q.push(s), dep[s] = 1; while (!q.empty()) { int u = q.front(); q.pop(); for (int i = lnk[u]; i; i = nxt[i]) { int v = ter[i]; if (val[i] && !dep[v]) { q.push(v), dep[v] = dep[u] + 1; } } } return dep[t]; } int dfs(int u, int t, int flow) { if (u == t) return flow; int ans = 0; for (int i = cur[u]; i && ans < flow; i = nxt[i]) { int v = ter[i]; if (val[i] && dep[v] == dep[u] + 1) { int x = dfs(v, t, std::min(val[i], flow - ans)); if (x) { val[i] -= x, val[i ^ 1] += x, ans += x; } } } if (ans < flow) dep[u] = -1; return ans; } void dinic(int s, int t) { while (bfs(s, t)) while (dfs(s, t, INF)); } int main() { scanf("%d%d", &n, &m); int s = 0, t = n + m + 1; for (int i = 1; i <= m; i++) { in…

「算法笔记」网络流 - 最大流
type: item
date: 2018-12-05T08:30:00+08:00
description: [scode type="green"]最大流，指一张网络图中的最大流量。[/scode]网络流系列文章最大流最小割费用流上下界网络流概念网络流网络流是指给定一个有向图，其中有两个特殊的点：源点 $s$（Source）和汇点 $t$（Sink）；每条边都有一个指定的流量上限，下文均称之为容量（Capacity），即经过这条边的流量不能超过容量，这样的图被称为网络流图。同时，除了源点和汇点外，所有点的入流和出流都相等，源点只有流出的流，汇点只有流入的流，网络流就是从 $s$ 到 $t$ 的一个可行流。可行流定义 $c(u,v)$ 表示边 $(u,v)$ 的容量，$f(u,v)$ 表示边 $(u,v)$ 的流量。如果满足 $0\le f(u,v)\le c(u,v)$，则称 $f(u,v)$ 为边 $(u,v)$ 上的流量。如果有一组流量满足：源点 $s$ 的流出量等于整个网络的流量，汇点 $t$ 的流入量等于整个网络的流量，除了任意一个不是 $s$ 或 $t$ 的点的总流入量等于总流出量。那么整个网络中的流量被称为一个可行流。最大流在所有可行流中，最大流指其中流量最大的一个流的流量。定义我们定义（部分定义在上文有涉及）：源点 $s$：只有流出量的点。汇点 $t$：只有流入量的点。容量 $c$：$c(u,v)$ 表示边 $(u,v)$ 上的容量。流量 $f$：$f(u,v)$ 表示边 $(u,v)$ 上的流量。残量 $w$：$w(u,v)$ 表示边 $(u,v)$ 上的残量（显然有 $w(u,v)=c(u,v)-f(u,v)$）。性质容量限制对于任何一条边，都有 $0\le f(u,v)\le c(u,v)$。斜对称性对于任何一条边，都有 $f(u,v)=-f(v,u)$。即从 $u$ 到 $v$ 的流量一定等于从 $v$ 到 $u$ 的流量的相反数。流守恒性对于任何一个点 $u$，如果满足 $u\neq s$ 并且 $u\neq t$，那么一定有 $\sum f(u,v)=0$，即 $u$ 到相邻节点的流量之和为 $0$。因为 $u$ 本身不会制造和消耗流量。求解増广路网络流的所有算法都基于増广路的思想，接下来首先介绍一下増广路思想。找到一条从 $s$ 到 $t$ 的路径，使得路径上的每一条边都有 $w(u,v)>0$ 即残量大于 $0$。注意：这里是严格 $>$ 而不是 $\ge$，这意味着这条边还可以分配流量。这条路径就被叫做増广路。找到这条路径上最小的 $w(u,v)$，记为 $flow$。将这条路径上的每一条边的 $w(u,v)$ 减去 $flow$。重复上述过程，直到找不到増广路为止。注意：其实上述方法并不是正确的，但这是一个非常重要的分析过程，因此请读者仔细阅读！我们可以根据这个过程在下面这张图中模拟一遍。如果我们把每条边的的信息用残量 / 容量表示出来，可以得到下图：假设我们第一次找到的増广路为 $1-2-3-4$，那么我们把这条路径上的边的 $w(u,v)$ 减去 $\min\{f(u,v)\}$ 即 $1$，得到下图：然后呢……我们发现已经没有増广路了，此时算出来的“最大流”为 $1$！但是我们可以手动计算一下，这张图的最大流其实是 $2$！这个最大流的路径为 $1-2-4$（流量为 $1$）和 $1-3-4$（流量为 $1$）。因此，我们可以发现这样的过程是错误的。原因就是増广路在一定意义上是有顺序的，说白了就是没有给它反悔的机会。所以我们要引入反向边的概念。反向边改进通过上文的分析我们已经知道，当我们在寻找増广路的时候，找到的并不一定是最优解。如果我们对正向边的 $w(u,v)$ 减去 $flow$ 的同时，将对应的反向边的 $w(v,u)$ 加上 $flow$，我们就相当于可以反悔从这条边流过。那么我们可以建立反向边，初始时每条边的 $w(u,v)=c(u,v)$，它的反向边的 $w(v,u)=0$（显然反向边不能有流量，因此残量为 $0$）。接下来再看一下上面那个例子，我们只用 $w(u,v)$ 来表示每条边（包括反向边）的信息：接下来开始寻找増广路，假如还是 $1-2-3-4$ 这条路径。我们需要把 $w(1,2)$，$w(2,3)$，$w(3,4)$ 减少 $1$，同时把反向边的 $w(2,1)$，$w(3,2)$，$w(4,3)$ 增加 $1$。那么可以得到下图：继续从 $s$ 开始寻找増广路（不需要考虑边的类型），显然可以发现路径 $1-3-2-4$，其中 $flow=1​$。更新边的信息，得到下图：此时我们发现没有増广路了，为了直观观察这个网络，我们去掉反向边，显然我们求出的最大流为 $2$！正确性当我们第二次増广边 $(2,3)$ 走这条反向边 $(3,2)$ 时，把 $(2,3)$ 和 $…