网络流问题

网络流是个很有用的东西，很多问题都可以转化为网络流。

目前本文会很快切入建图，证明什么有时间再补。

概述

一个网络是一张有向图 $G=(V,E)$ ，对于每条有向边 $(u,v)\in E$ 存在容量限制 $c(u,v)$ ，当 $(u,v)\not\in E$ 时， $c(u,v)=0$ 。网络的可行流分为有源汇（指定了两个节点 $s,t$ ，代表图的源点和汇点）和无源汇，但是都存在一个定义域为节点二元组的流函数 $f(x,y)$ ， $f(x,y)$ 代表边 $x\rightarrow y$ 的流量，满足：

$f$ 满足容量限制： $f(x,y)\le c(x,y)$ ，当两者相等时， $x\rightarrow y$ 就流满了；
斜对称性质： $f(x,y)=-f(y,x)$ ，也就是说，反向边其实是负的流量^[1]；
流量守恒：除源点和汇点外（当然只限于有源汇可以除了这两个节点），从每个节点流入和流出的流量相等，即 $\forall i\ne s,t,\sum f(u,i)=\sum f(i,v)$ ，也就是说，每个节点不储存流量，进去多少就流出来多少。

以下是一些定义：

对于有源汇，有 $\sum f(S,i)=\sum f(i,T)$ ，此时这个相等的和成为当前流 $f$ 的流量。
定义流 $f$ 在网络 $G$ 上的残量网络 $G_f=(V,E_f)$ 为容量函数 $c_f=c-f$ 。根据容量限制， $c_f(x,y)\ge 0$ ，当 $c_f(x,y)=0$ 时，则视为 $x\rightarrow y$ 在残量网络上不存在。也就是说，在残量网络中我们要删掉满流边。
定义增广路 $P$ 是残量网络 $G_f$ 上源点到汇点的一条路径，而无源汇则没有增广路。
将点集分为两个互补相交的 $A,B$ ，且满足 $S\in A, T\in B$ ，这种划分方式称为割，割的容量为 $\sum_{u\in A}\sum_{v\in B}c(u,v)$ ，流量为 $\sum_{u\in A}\sum_{v\in B}f(u,v)$ 。如果 $u\in A,v\in B$ ，那么 $(u,v)$ 是割边，可以看出，割边一般不止一条。

接下来讨论的内容默认都是有源流！

最大流问题

最大流是求一个网络的最大流量。

增广

找到一条残量网络 $G_f$ 上的增广路 $P$ ，并为 $P$ 上的每一条边增加 $c_f(P)=\min_{(u,v)\in P}c_f(u,v)$ 的流量。也就是说，流量能流满就能流满。这一过程称之为增广。

怎样证明这个贪心策略？不需要！实际上在当前边的流量增加 $c_f(x,y)$ 时，我们要给它的反向边的容量增加 $c_f(y,x)$ ，其实这是一个反悔贪心的策略，可以回收原来的流量，正确性得以保证。

最大流最小割定理

割中割边容量和最小的划分方式称为最小割，而且最大流等于最小割。证明如下：

存在一组流的流量等于一组割的容量：只需要让割边流满即可，最大流存在的时候残量网络不连通，也就提供了一组割。
任意一组流的流量不大于任意一组割的容量。如果割掉这些边，那么网络流量尚未最大化，仍然可以找到增广路，与最大流的求解方式矛盾。

Dinic 算法

Edmonds-Karp 和其他高级算法在本文中不会出现，只会介绍 Dinic。

模板。

Dinic 会不断进行 bfs 来在残量网络上构造分层图（根据节点的层次 $d[x]$ ，从 $S$ 到 $x$ 最少需要经过的边数），然后在分层图上进行 dfs 寻找增广路。时间复杂度为 $O(n^2m)$ 。

查看代码

#include <bits/stdc++.h>
using namespace std;
typedef long long i64;
const i64 INF = 1e18;

struct edge {
    int u, v, w;
    edge(int u = 0, int v = 0, int w = 0) : u(u), v(v), w(w) {}
};

int n, m, s, t, d[1205], cur[1205]; // cur 为当前弧下标
vector<int> G[1205];
vector<edge> edges;

inline void addedge(int u, int v, int w) {
    edges.emplace_back(edge(u, v, w));
    G[u].emplace_back(edges.size() - 1);
}

bool bfs(void) {
    memset(cur, 0, sizeof(cur));
    memset(d, -1, sizeof(d));
    queue<int> q;
    q.push(s); d[s] = 1;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = 0; i < G[u].size(); ++i) {
            edge &e = edges[G[u][i]];
            if (e.w && d[e.v] == -1) {
                q.push(e.v);
                d[e.v] = d[u] + 1;
                if (e.v == t) return true;
            }
        }
    }
    return false;
}

i64 dinic(int x, i64 res) {
    if (x == t || res == 0) return res;
    i64 flow = 0;
    for (int i = cur[x]; i < G[x].size() && res; ++i) {
        edge &e = edges[G[x][i]]; cur[x] = i;
        i64 c = min(res, (i64)e.w);
        if (d[e.v] == d[x] + 1 && c) {
            i64 k = dinic(e.v, c);
            flow += k; res -= k; 
            edges[G[x][i]].w -= k; edges[G[x][i] ^ 1].w += k;
        }
    }
    if (!flow) d[x] = -1;
    return flow;
}

int main(void) {
    scanf("%d%d%d%d", &n, &m, &s, &t);
    while (m--) {
        int u, v, w; scanf("%d%d%d", &u, &v, &w);
        addedge(u, v, w); addedge(v, u, 0);
    }
    i64 flow = 0, maxflow = 0;
    while (bfs()) while (flow = dinic(s, INF)) maxflow += flow;
    printf("%lld\n", maxflow);
    return 0;
}

无负环费用流

指的是最小费用最大流，也就是说，在原有网络的基础上，每一条边多了一个权值 $w(x,y)$ ，要求在保证最大流前提下，找出 $\sum_{(x,y)\in E} f(x,y)\times w(x,y)$ 的最小值。通常使用 SPP 算法解决这个问题。

SSP 实现时只需要将 Dinic 的 bfs 替换为 SPFA 即可（每条边的长度为权值 $w$ ）。相应的地方改一下即可。理论上限时间复杂度很高，但是实际表现不错，而且业界公约不卡。

模板，代码如下：

查看代码

#include <bits/stdc++.h>
using namespace std;
typedef long long i64;
const i64 INF = 1e18;

struct edge {
    int u, v, w, c;
    edge(int u = 0, int v = 0, int w = 0, int c = 0) : 
        u(u), v(v), w(w), c(c) {}
};

int n, m, s, t, cur[5005], d[5005];
bool inq[5005];
vector<int> G[5005];
vector<edge> edges;

inline void addedge(int u, int v, int w, int c) {
    edges.emplace_back(edge(u, v, w, c));
    G[u].emplace_back(edges.size() - 1);   
}

bool SPFA(void) {
    memset(cur, 0, sizeof(cur));
    memset(d, 0x3f, sizeof(d));
    queue<int> q; q.push(s); d[s] = 0; inq[s] = true;
    while (!q.empty()) {
        int u = q.front(); q.pop(); inq[u] = false;
        for (int i = 0; i < G[u].size(); ++i) {
            edge &e = edges[G[u][i]];
            if (e.w && d[e.v] > d[u] + e.c) {
                d[e.v] = d[u] + e.c;
                if (!inq[e.v]) q.push(e.v), inq[e.v] = true;
            }
        }
    }
    return d[t] < 0x3f3f3f3f;
}

i64 cost;
bool vis[5005];
i64 dinic(int x, i64 res) {
    if (x == t) return res;
    i64 flow = 0; vis[x] = true;
    for (int i = cur[x]; i < G[x].size() && res; ++i) {
        edge &e = edges[G[x][i]]; cur[x] = i;
        i64 c = min(res, i64(e.w));
        if (!vis[e.v] && c && d[e.v] == d[x] + e.c) {
            i64 k = dinic(e.v, c);
            flow += k; cost += k * e.c; res -= k;
            edges[G[x][i]].w -= k; edges[G[x][i] ^ 1].w += k;
        }
    }
    if (!flow) d[x] = 0x3f3f3f3f;
    vis[x] = false;
    return flow;
}

int main(void) {
    scanf("%d%d%d%d", &n, &m, &s, &t);
    while (m--) {
        int u, v, w, c; scanf("%d%d%d%d", &u, &v, &w, &c);
        addedge(u, v, w, c); addedge(v, u, 0, -c);
    }
    i64 maxflow = 0, flow;
    while (SPFA()) while (flow = dinic(s, INF)) maxflow += flow;
    printf("%lld %lld\n", maxflow, cost);
    return 0;
}

解题思路

网络流本质上是一种反悔贪心，将贪心的反悔策略用一条反向边简单的表示。在解题时，关键在于找到题目中的方案和一种流或割对应。我们来看一个例子：

[SHOI2007] 善意的投票。

幼儿园里有 $n$ 个小朋友打算通过投票来决定睡不睡午觉。
虽然每个人都有自己的主见，但是为了照顾一下自己朋友的想法，他们也可以投和自己本来意愿相反的票。
我们定义一次投票的冲突数为好朋友之间发生冲突的总数加上和所有和自己本来意愿发生冲突的人数。
给出每个小朋友的意愿和每一对好朋友。我们的问题就是，每位小朋友应该怎样投票，才能使冲突数最小？输出可能的最小冲突数。

对于 $100\%$ 的数据， $2\le n\le300$ ， $1\le m \le \frac{n(n-1)}2$ 。

这看起来很像一个最小割的模型，考虑如何使用一组割来表示一种意见方案。每割掉一条边需要付出 $1$ 的代价。于是将支持的小朋友与 $S$ 连边，反对的小朋友与 $T$ 连边，每对朋友之间连边，求出图的最小割即可。这其实是一个集合划分模型。

查看代码

#include <bits/stdc++.h>
using namespace std;

int n, m;
struct edge {
    int u, v, w;
    edge(int u = 0, int v = 0, int w = 0) : u(u), v(v), w(w) {}
};

vector<edge> edges;
vector<int> G[305];
int d[305], cur[305];

inline void addedge(int u, int v, int w) {
    edges.emplace_back(edge(u, v, w));
    G[u].emplace_back(edges.size() - 1);
}

bool bfs(void) {
    memset(d, -1, sizeof(d)); memset(cur, 0, sizeof(cur));
    queue<int> q; q.push(0); d[0] = 1;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = 0; i < G[u].size(); ++i) {
            edge &e = edges[G[u][i]];
            if (e.w && d[e.v] == -1) {
                q.push(e.v); d[e.v] = d[u] + 1;
                if (e.v == n + 1) return true;
            }
        }
    }
    return false;
}

int dinic(int x, int res) {
    if (x == n + 1 || res == 0) return res;
    int flow = 0;
    for (int i = cur[x]; i < G[x].size(); ++i) {
        edge &e = edges[G[x][i]]; cur[x] = i;
        int c = min(res, e.w);
        if (d[e.v] == d[x] + 1 && c) {
            int k = dinic(e.v, c);
            flow += k; res -= k;
            edges[G[x][i]].w -= k; edges[G[x][i] ^ 1].w += k;
        }
    }
    if (!flow) d[x] = -1;
    return flow;
}

int type[305];
int main(void) {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", type + i);
        if (type[i]) addedge(0, i, 1), addedge(i, 1, 0);
        else addedge(i, n + 1, 1), addedge(n + 1, i, 0);
    }
    while (m--) {
        int u, v; scanf("%d%d", &u, &v);
        if (type[u] == 0 && type[v] == 1) swap(u, v);
        addedge(u, v, 1); addedge(v, u, 0);
    }
    int flow = 0, maxflow = 0;
    while (bfs()) while (flow = dinic(0, 1e9)) maxflow += flow;
    printf("%d\n", maxflow);
    return 0;
}

如果要求输出集合划分模型的一组方案，那么就看残余网络上的 $s$ 到每个点的距离。如果能走到就是在 $A$ ，否则就是在 $B$ 。

上下界网络流

有的题目的流量限制除了有上界，还有下界。

网络流常见模型

我们来看一些网络流的常见模型。

点边转化 | 最小割点

如果删去点 $i$ 有代价 $w_i$ ，求使得 $S,T$ 不连通的最小代价？

将每个点拆成入点 $i_{in}$ 和出点 $i_{out}$ ，在它们之间连一条容量为 $w_i$ 的边，表示删去这个点。对于原图的每一条边 $u,v$ ，连接 $u_{out}\rightarrow v_{in}$ 一条 $+\infty$ 容量的边，这样我们只能删点而不会割边。

集合划分模型

这个内容非常常见。

$\min_{x_1,x_2,\cdots x_n\in\{0,1\}}\sum_{(u,v)\in E} c_{u,v}x_u\overline{x_v}+\sum_{u}a_ux_u+b_u\overline{x_u}$

说的就是为 $x_i$ 选定合适的值，使得和式的值最小。

连 $S\rightarrow i$ 的容量为 $b_i$ 的边， $i\rightarrow T$ 的容量为 $a_i$ 的边。如果割掉了 $i\rightarrow T$ ，说明将 $i$ 划分到了集合 $A$ ，代价为 $a_i$ 。

给 $u,v$ 连容量限制为 $c_{u,v}$ 的双向边，这样如果 $u,v$ 不属于同一集合，至少会割掉其中一条边。

这样这个网络的最小割就是答案。

还有一种限制： $x$ 在集合 $A$ 且 $y$ 在集合 $B$ 时有代价 $w$ ，那么连 $x\rightarrow y$ 的容量为 $w$ 的边，这样如果 $x$ 和 $S$ 相连且 $y$ 和 $T$ 相连，那么这条边需要被割掉。

如何输出方案？要注意什么是割边：在最后的残量网络上 $d(x)$ 是否存在，存在则属于集合 $A$ ，否则是集合 $B$ 。

最大权闭合子图

一张有向图 $G=(V,E)$ 的闭合子图 $G'$ 定义在点集 $V'\subseteq V$ 上，一个点集 $V'$ 符合要求当且仅当 $V'$ 内部每个点的所有出边仍指向 $V'$ ，即点集内部每个点在有向图上能够到达的点仍然属于该点集。

而最大权闭合子图则是每个点有点权，求闭合子图的最大权值。

考虑集合划分模型，对于每个节点，可以将其划分到选或不选的集合中，也就是 $S\rightarrow i$ 连 $0$ ， $i\rightarrow T$ 连 $w_i$ 。如果 $(u,v)\in E$ ，就是如果 $u$ 分到选的集合中， $v$ 也必须分到选的集合中，即 $u\rightarrow v$ 有容量 $-\infty$ ，求网络的最大割即可。

但是最大割是 NPH 的，因此考虑取相反数求最小割。然而这样会出现负容量的边！将负容量的边改到 $S\rightarrow i$ 来连。这样答案为所有正权值的和减去最小割即可。

模板，代码如下：

查看代码

#include <bits/stdc++.h>
using namespace std;

int m, n, ans; 

struct edge {
    int v, w; 
    edge(int v = 0, int w = 0) : v(v), w(w) {}
};

struct Graph {
    int S, T, cur[205], d[205]; 
    vector<edge> edges; 
    vector<int> G[205]; 
    inline void addedge(int u, int v, int w) {
        edges.emplace_back(edge(v, w));
        G[u].emplace_back(edges.size() - 1);
        edges.emplace_back(edge(u, 0));
        G[v].emplace_back(edges.size() - 1);  
    }
    bool bfs(void) {
        memset(cur, 0, sizeof cur); memset(d, -1, sizeof d);
        queue<int> q; q.push(S); d[S] = 1; 
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int i = 0; i < G[u].size(); ++i) {
                edge &e = edges[G[u][i]];
                if (e.w && d[e.v] == -1) {
                    d[e.v] = d[u] + 1; q.push(e.v); 
                    if (e.v == T) return true; 
                }
            }
        }
        return false; 
    }
    int dinic(int x, int res) {
        if (x == T) return res; 
        int flow = 0; 
        for (int i = cur[x]; i < G[x].size() && res; ++i) {
            edge &e = edges[G[x][i]]; cur[x] = i; 
            int c = min(res, e.w); 
            if (d[e.v] == d[x] + 1 && c) {
                int k = dinic(e.v, c); flow += k; res -= k; 
                edges[G[x][i]].w -= k; edges[G[x][i] ^ 1].w += k; 
            }
        }
        if (!flow) d[x] = -1;
        return flow; 
    }
    int maxFlow(int s, int t) {
        S = s, T = t; 
        int flow, maxflow = 0; 
        while (bfs()) while (flow = dinic(S, 1e9)) maxflow += flow; 
        return maxflow;
    }
} G;

int main(void) {
    scanf("%d%d", &m, &n); 
    for (int i = 1; i <= m; ++i) {
        int w, x; scanf("%d", &w); G.addedge(0, i, w); ans += w; 
        while (scanf("%d", &x) == 1 && x) G.addedge(i, x + m, 1e9); 
    }
    for (int i = 1, w; i <= n; ++i) scanf("%d", &w), G.addedge(i + m, n + m + 1, w); 
    printf("%d\n", ans - G.maxFlow(0, n + m + 1)); 
    return 0;
}

二分图

设无向图 $G=(V,E)$ ，若能够将 $V$ 分成两个点集 $V_1,V_2$ 满足 $V_1\cap V_2=\varnothing,V_1\cup V_2=V$ 且 $\forall(u,v)\in E,u\in V_1,v\in V_2$ （也可以反过来），这样 $G$ 是一张二分图， $V_1,V_2$ 分别称为左部点和右部点。

二分图的充要条件是不存在奇环，这样我们可以给二分图进行黑白染色。

从某个点开始 DFS，遍历当前点 $u$ 和邻居 $v$ ，如果 $v$ 未被访问，则 $v$ 的颜色与 $u$ 相反；如果访问过，说明存在奇环。

二分图匹配

给定二分图 $G=(V,E)$ ，若边集 $M\subseteq E$ 满足 $M$ 中任意两条边不交于同一端点，则称 $M$ 是 $G$ 的一组匹配，其大小为 $|M|$ 。

特别的，若 $|V_1|=|V_2|,|M|=|V_1|$ ，则称 $M$ 为完美匹配。

最大匹配

我们希望求出边集 $M$ 的最大大小。

显然，我们从 $S$ 向 $V_1$ 的所有点连一条 $1$ 的边， $V_2$ 向 $T$ 连一条 $1$ 的边，根据 $E$ 从 $V_1$ 向 $V_2$ 连边，跑最大流即可。在这里 Dinic 的时间复杂度为 $O(m\sqrt{n})$ 。

最大多重匹配

即节点 $u$ 不能与超过 $L_u$ 条边相连，这样只需要将每个点与源点或汇点的容量设为 $L_u$ 即可。时间复杂度依然正确。

匈牙利算法

匈牙利算法可以以 $O(nm)$ 的时间复杂度解决二分图的最大匹配问题。

工作过程如下：

加入一个左部点 $u$ ，然后让 $u$ 去尝试匹配。
如果 $u$ ，已经匹配，则增广失败。
遍历 $u$ $u$ 能到达的所有右部点 $v$ $v$ ：
- $y$ 被访问过了，那么直接再见。
- $y$ 没被匹配，让 $x$ 匹配 $y$ ，增广成功。
- $y$ 被匹配，考虑 $y$ 原来匹配的 $x'$ ，如果 $x'$ 还能够成功匹配，那么改为让 $y$ 匹配 $x$ ，形成新的增广路。

实际上，如果当前点失配，vis 数组是不需要清空的！模板，代码如下：

int n, m, E, mch[505], vis[505];
vector<int> G[505];

bool dfs(int x) {
	if (vis[x]) return 0; vis[x] = 1; 
  	for (int y : G[x])
    	if (!mch[y] || dfs(mch[y])) return mch[y] = x, 1;
	return 0;
}

int main(void) {
  	cin >> n >> m >> E;
  	for(int i = 1; i <= E; i++) {
    	int u, v; cin >> u >> v;
    	G[u].push_back(v);
  	}
  	int ans = 0;
  	for (int i = 1; i <= n; i++) if (dfs(i)) {
    	memset(vis, 0, sizeof(vis));
    	++ans; 
  	}
  	cout << ans << endl;
  	return 0;
}

二分图相关问题

二分图有一些常见问题。我们来看：

最小点覆盖集

给定二分图 $G=(V,E)$ ，若点集 $C\subseteq V$ 满足对于任意 $(u,v)\in E$ 都有 $u\in C$ 或 $v\in C$ ，则称 $C$ 是 $G$ 的点覆盖集。

考虑一组点覆盖集，不存在边 $(u,v)\in E$ 使得 $u,v$ 同时不属于 $C$ ，这是集合划分模型？但是有问题，我们要设置在同一个集合是代价是无穷的，集合划分模型没有这样的操作。

但是 $G$ 是二分图，任意一条边连接两部点，因此考虑将一部分点的状态取反。即左部点与 $S$ 不连通表示它不属于 $C$ ，但右部点与 $S$ 连通表示它属于 $C$ 。这样限制就会变为，如果左部点 $u$ 与 $S$ 连通， $u,v$ 之间有连边，但是右部点 $v$ 与 $T$ 连通，则 $u,v$ 同时不属于 $C$ ，不合法。

我们将两部点之间的连边容量设为 $+\infty$ ，对该网络求最大流，就是最小点覆盖集大小。由于每个点最多流入或流出 $1$ 的流量，因此两部点之间的连边容量可以设为 $1$ ，这证明了最小点覆盖集大小等于最大匹配。

它可以求解这样的问题：对于每条限制 $lim$ 恰有两种方案 $u,v$ 能满足，求最少需要选择多少种方案满足所有限制。

最大独立集

给定二分图 $G=(V,E)$ ，若点集 $I\subseteq V$ 满足任意两点不直接相连，则称 $I$ 是 $G$ 的独立集。二分图最大独立集等于 $V$ 减去最小点覆盖集。

模板，代码如下：

查看代码

#include <bits/stdc++.h>
using namespace std;

int n, m; 
struct edge {
    int v, w; 
    edge(int v = 0, int w = 0) : v(v), w(w) {}
};
struct Graph {
    int s, t, cur[1005], d[1005]; 
    vector<edge> edges; 
    vector<int> G[1005]; 
    inline void addedge(int u, int v, int w) {
        edges.emplace_back(v, w); 
        G[u].emplace_back(edges.size() - 1); 
        edges.emplace_back(u, 0);
        G[v].emplace_back(edges.size() - 1); 
    }
    bool bfs(void) {
        memset(cur, 0, sizeof cur); 
        memset(d, -1, sizeof d);
        queue<int> q; q.push(s); d[s] = 1; 
        while (!q.empty()) {
            int u = q.front(); q.pop(); 
            for (int i = 0; i < G[u].size(); ++i) {
                edge &e = edges[G[u][i]]; 
                if (e.w && d[e.v] == -1) {
                    q.push(e.v); d[e.v] = d[u] + 1; 
                    if (e.v == t) return 1; 
                }
            }
        }
        return 0; 
    }
    int dinic(int x, int res) {
        if (x == t) return res; 
        int flow = 0; 
        for (int i = cur[x]; i < G[x].size(); ++i) {
            edge &e = edges[G[x][i]]; cur[x] = i; 
            int c = min(res, e.w);
            if (d[e.v] == d[x] + 1 && c) {
                int k = dinic(e.v, c); 
                flow += k; res -= k; 
                edges[G[x][i]].w -= k; edges[G[x][i] ^ 1].w += k;
            }
        }
        if (!flow) d[x] = -1; 
        return flow; 
    }
    int maxflow(int S, int T) {
        s = S, t = T; 
        int maxflow = 0, flow = 0; 
        while (bfs()) while (flow = dinic(s, 1e9)) maxflow += flow; 
        return maxflow; 
    }
} G;

int col[1005]; 
vector<int> E[1005]; 
void dfs(int x) {
    if (col[x]) G.addedge(0, x, 1);
    else G.addedge(x, n + 1, 1); 
    for (int y : E[x]) {
        if (col[y] == -1) col[y] = col[x] ^ 1, dfs(y); 
        if (col[x]) G.addedge(x, y, 1); 
    }
}

int main(void) {
    scanf("%d%d", &n, &m); 
    while (m--) {
        int u, v; scanf("%d%d", &u, &v); ++u; ++v; 
        E[u].emplace_back(v); E[v].emplace_back(u); 
    }
    memset(col, -1, sizeof col); 
    for (int i = 1; i <= n; ++i)
        if (col[i] == -1) col[i] = 1, dfs(i); 
    printf("%d\n", n - G.maxflow(0, n + 1)); 
    return 0;
}

Problemset

最重要的还是那些经典模型，然后进行大量题目训练。

网络流 24 题

没有固定的顺序（但基本上按照难度排序）。虽然非常老，但是其中有些建模方式相当经典。

网络流问题

概述

最大流问题

增广

最大流最小割定理

Dinic 算法

无负环费用流

解题思路

上下界网络流

网络流常见模型

点边转化 | 最小割点

集合划分模型

最大权闭合子图

二分图

二分图匹配

最大匹配

最大多重匹配

匈牙利算法

二分图相关问题

最小点覆盖集

最大独立集

Problemset

网络流 24 题

软件补丁问题

孤岛营救问题

试题库问题

飞行员配对方案问题

圆桌问题

太空飞行计划问题

骑士共存问题

最长不下降子序列问题

最小路径覆盖问题

魔术球问题

简单网络流

[USACO05NOV] Asteroids G

[THUPC2022 初赛] 分组作业

[Luogu P1402] 酒店之王

[Luogu P4313] 文理分科

二分图

「Wdoi-6」最澄澈的空与海

[CF1139E] Maximize Mex

[CF1592F] Alice and Recoloring

综合应用

[CF1728F] Fishermen

[WC2007] 剪刀石头布