「网络流浅谈」最小割的模型

最大权闭合子图

引入 Introduction

闭合子图指对于子图 $G=(V,E)$，$\mathrm{\forall }u\in V,(u,v)\in E$，都有 $v\in V$。

最大权闭合子图无非就是对于所有的闭合子图 $G$ 中 $\sum _{u\in V}{w}_u$ 最大的闭合子图。

对于这个图中，闭合子图有哪些呢？

红色框圈画出的即为 $1$ 个闭合子图，因为对于任意一个点所连向的点都在该子图内。

主算法 Main Algorithm

不难发现任意一个割所划分成的 $2$ 个集合均为闭合子图，而我们要求最大权闭合子图，故考虑如何求解。

建立一个流网络，将源点向所有权值为正的点连一条长度为该点权值的边，将所有权值为负数的点向汇点连一条长度为该点权值的绝对值的边。对于原图中的边，在流网络中均为 $+\mathrm{\infty }$。

对于割 $[S,T]$，$c(S,T)=\sum _{(u,v)\in E,u\in S,v\in T}c(u,v)$，由于中间的边权均为 $+\mathrm{\infty }$，所以只会割两边的边，即 $c(S,T)=\sum _{(s,v)\in E,v\in T}c(s,v)+\sum _{(u,t)\in E,u\in S}c(u,t)$。

又因为建图的时候 $s$ 所连向的边，均为连向点的边权；而连向 $t$ 的边的边权均为连向他点的权值。故，$c(S,T)=\sum _{(s,v)\in E,v\in T}c(s,v)+\sum _{(u,t)\in E,u\in S}c(u,t)=\sum _{(s,v)\in E,v\in T}{w}_v-\sum _{(u,t)\in E,u\in S}{w}_u$

考虑最大权闭合子图的权值为什么？$val=\sum _{(s,v)\in E,v\in S}{w}_v+\sum _{(u,t)\in E,u\in S}{w}_u$。

不难发现第二项是完全一样的：所以将 $c(S,T)$ 与 $val$ 相加得，$c(S,T)+val=\sum _{(s,v)\in E,v\in T}{w}_v+\sum _{(s,v)\in E,v\in S}{w}_v$

由于 $S$ 与 $T$ 共同构成了点集 $V$，故 $\sum _{(s,v)\in E,v\in T}{w}_v+\sum _{(s,v)\in E,v\in S}{w}_v=\sum _{(s,v)\in E}{w}_v=\sum _{w_v>0}{w}_v$

综上所述，$val=\sum _{w_v>0}{w}_v-c(S,T)$，通过数学知识推理得 $c(S,T)$ 应最小，即求最小割。

P4174 [NOI2006] 最大获利

模版题，按照上述做法建图即可。

#include 
#define fi first
#define se second
#define int long long

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

const int N = 6e4 + 10, M = 4e5 + 10, INF = 1e18;

int n, m, s, t;
int a[N], b[N];
int h[N], e[M], ne[M], f[M], idx;
int dist[N], cur[N];

void add(int a, int b, int c) {
	e[idx] = b, ne[idx] = h[a], f[idx] = c, h[a] = idx ++;
	e[idx] = a, ne[idx] = h[b], f[idx] = 0, h[b] = idx ++;
}
bool bfs() {
	memset(dist, -1, sizeof dist);
	queue<int> q;
	q.emplace(s), dist[s] = 0, cur[s] = h[s];
	while (q.size()) {
		auto u = q.front();
		q.pop();

		for (int i = h[u]; ~i; i = ne[i]) {
			int v = e[i];
			if (dist[v] == -1 && f[i]) {
				dist[v] = dist[u] + 1, cur[v] = h[v];
				if (v == t) return 1;
				q.emplace(v);
			}
		}
	}
	return 0;
}
int find(int u, int lim) {
	if (u == t) return lim;

	int flow = 0;
	for (int i = cur[u]; ~i && flow < lim; i = ne[i]) {
		cur[u] = i;
		int v = e[i];
		if (dist[v] == dist[u] + 1 && f[i]) {
			int tmp = find(v, min(f[i], lim - flow));
			if (!tmp) dist[v] = -1;
			flow += tmp, f[i] -= tmp, f[i ^ 1] += tmp;
		}
	}

	return flow;
}
int dinic() {
	int res = 0, flow;
	while (bfs()) while (flow = find(s, INF)) res += flow;
	return res;
}

signed main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	cin >> n >> m;
	memset(h, -1, sizeof h);

	s = 0, t = n + m + 1;
	for (int i = 1; i <= n; i ++)
		cin >> a[i];
	for (int i = 1; i <= m; i ++) {
		int u, v;
		cin >> u >> v >> b[i];
		add(i + n, u, INF), add(i + n, v, INF);
	}

	int tot = 0;
	for (int i = 1; i <= m; i ++)
		add(s, i + n, b[i]), tot += b[i];
	for (int i = 1; i <= n; i ++)
		add(i, t, a[i]);

	cout << tot - dinic() << endl;

	return 0;
}

最大密度子图

引入 Introduction

定义无向图 $G=(V,E)$ 的密度为 $\frac{|E|}{|V|}$。则，对于一个无向图 $G=(V,E)$，令 $G$ 的子图 $G^{\prime }=(V^{\prime },E^{\prime })$，满足 $\mathrm{\forall }(u,v)\in E^{\prime },u\in V^{\prime },v\in V^{\prime }$。对于所有满足条件的子图 $G$ 中，密度最大的即为最大密度子图。

主算法 Main Algorithm

对于形式 $\frac{|E|}{|V|}$，不难想到通过分数规划求解，即二分 $g$，如果 $\frac{|E|}{|V|}\ge g$，则说明 $g$ 还可以更大，调整二分左端点；反之，调整二分右端点。

将式子继续化简可以得到：$|E|-g|V|\ge 0$，也就是求 $|E|-g|V|$ 的最大值，即 $g|V|-|E|$ 的最小值。

最小割是可以解决点集的，但是难以算出边数的多少。所以，考虑如何将边数加入割。

考虑红色圈出的子图，如何计算边数呢？可以考虑使用度数，某个点度数减去该点连向集合外部的边的个数再除 $2$，即可得到集合内边的个数，即 $\frac{\sum _{u\in V}{d}_u-c(V,\overline{V})}{2}$。这样，就与割产生了关系。

继续推式子：$g|V|-|E|=\sum _{u\in V}g-\frac{\sum _{u\in V}{d}_u-c(V,\overline{V})}{2}=\sum _{u\in V}(g-\frac{d_u}{2})+\frac{c(V,\overline{V})}{2}$

为了使与最小割有单调关系，将割 $c(V,\overline{V})$ 的系数提出得 $\frac{\sum _{u\in V}(2g-d_u)+c(V,\overline{V})}{2}$

那么，就可以建图了。对于任意一个点 $u$ 均向汇点 $t$ 连一条边权为 $2g-d_u$ 的边，不过由于 $2g-d_u$ 可能会小于 $0$，所以边权应为 $2g-d_u+U$，其中 $U$ 为常数。对于点之间的边，即为原图的边，为了算边数所以边权均为 $1$。源点 $s$ 向任意一个点连一条边权为 $U$ 的边即可。$U$ 取 $|E|$ 即可，因为 $d_u$ 不可能超过 $|E|$。下图为一个例子。

建完图后，由于部分边权多加了 $U$，所以考虑新图最小割 $c^{\prime }(S,T)$ 与 $|E|-g|V|$ 的关系。令 $P=S-\{s\},P^{\prime }=\overline{P}-\{t\}$，则最小割的边集分为 $4$ 种情况：$P\to \{t\},\{s\}\to P^{\prime },P\to P^{\prime },\{s\}\to \{t\}$。不过，最后一种边不存在舍去。

$$\begin{array}{rl}{c}^{\prime }(S,T)=& \sum _{u\in P}(U+2g-d_u)+\sum _{v\in P^{\prime }}U+\sum _{u\in P}\sum _{v\in P^{\prime }}c(u,v)\\ =& \sum _{u\in P}(U+2g-d_u+\sum _{v\in P^{\prime }}c(u,v))+\sum _{v\in P^{\prime }}U\\ =& \sum _{u\in P}(U+2g-(d_u-\sum _{v\in P^{\prime }}c(u,v)))+\sum _{v\in P^{\prime }}U\\ =& \sum _{u\in P}(U+2g-\sum _{v\in P}c(u,v))+\sum _{v\in P^{\prime }}U\leftarrow u\mathrm{所}\mathrm{有}\mathrm{出}\mathrm{边}-\mathrm{向}\mathrm{集}\mathrm{合}\mathrm{外}\mathrm{边}=\mathrm{向}\mathrm{集}\mathrm{合}\mathrm{内}\mathrm{边}\\ =& \sum _{u\in P}2g-\sum _{u\in P}\sum _{v\in P}c(u,v)+\sum _{v\in P^{\prime }}U+\sum _{v\in P}U\\ =& |P|2g+2|E|+U\cdot n\end{array}$$

故，$|E|-g|V|=\frac{U\cdot n-c^{\prime }(S,T)}{2}$，这里 $V$ 与 $P$ 等价，都是我们选出的点。到此，该问题得以解决。

POJ3155 - Hard Life

模版题，使用上述做法建图计算即可。

对于输出方案，选择的集合其实就是最小割中 $S$ 集合，那么怎么找出呢？只需要从 $s$ 每次走 $>0$ 的边所能到达的点的集合，便是答案（注意：不能包含 $s$）。

#include 
#define fi first
#define se second
#define int long long

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

const int N = 1e2 + 10, M = 3e3 + 10;
const double eps = 1e-6;

int n, m, s, t;
int h[N], e[M], ne[M], idx;
double f[M];
int d[N], cur[N], dg[N], st[N];
vector<int> res;
std::vector<PII> E;

void add(int a, int b, double c1, double c2) {
	e[idx] = b, ne[idx] = h[a], f[idx] = c1, h[a] = idx ++;
	e[idx] = a, ne[idx] = h[b], f[idx] = c2, h[b] = idx ++;
}
bool bfs() {
	memset(d, -1, sizeof d);
	queue<int> q;
	q.emplace(s), d[s] = 0, cur[s] = h[s];
	while (q.size()) {
		int u = q.front();
		q.pop();

		for (int i = h[u]; ~i; i = ne[i]) {
			int v = e[i];
			if (d[v] == -1 && f[i] > 0) {
				d[v] = d[u] + 1, cur[v] = h[v];
				if (v == t) return 1;
				q.emplace(v);
			}
		}
	}
	return 0;
}
double find(int u, double lim) {
	if (u == t) return lim;

	double flow = 0;
	for (int i = cur[u]; ~i && flow < lim; i = ne[i]) {
		cur[u] = i;
		int v = e[i];
		if (d[v] == d[u] + 1 && f[i] > 0) {
			double tmp = find(v, min(lim - flow, f[i]));
			if (tmp <= 0) d[v] = -1;
			f[i] -= tmp, f[i ^ 1] += tmp, flow += tmp;
		}
	}

	return flow;
}
void build(double g) {
	memset(h, -1, sizeof h);
	idx = 0;
	for (auto v : E) add(v.fi, v.se, 1, 1);
	for (int i = 1; i <= n; i ++) add(s, i, m, 0);
	for (int i = 1; i <= n; i ++) add(i, t, 2.0 * g - dg[i] + m, 0);
}
bool dinic(double g) {
	build(g);
	double res = 0, flow;
	while (bfs()) while (flow = find(s, 1e18)) res += flow;
	return res < m * n * 1.0;
}
void dfs(int u) {
	if (u != s) res.emplace_back(u);
	st[u] = 1;
	for (int i = h[u]; ~i; i = ne[i]) {
		int v = e[i];
		if (!st[v] && f[i] > 0) dfs(v);
	}
}

signed main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	cin >> n >> m;

	s = 0, t = n + 1;
	for (int i = 1; i <= m; i ++) {
		int u, v;
		cin >> u >> v;
		E.emplace_back(u, v), dg[u] ++, dg[v] ++;
	}

	double l = 0, r = m;
	while (r - l > eps) {
		double mid = (l + r) * 0.5;
		if (dinic(mid)) l = mid;
		else r = mid;
	}

	dinic(l), dfs(s);
	if (!res.size()) {
		cout << "1\n1";
		return 0;
	}
	cout << res.size() << endl;
	sort(res.begin(), res.end());
	for (auto v : res)
		cout << v << endl;
	cout << endl;

	return 0;
}

最小权点覆盖集

引入 Introduction

点覆盖集指选择点集 $V$，使得对于边集 $E$ 中的每一条边，至少有一个端点在点集 $V$ 中。

最小权点覆盖集指在所有点覆盖集中，点的权值和最小的点集。

主算法 Main Algorithm

最小权点覆盖集只有在二分图的情况下才存在高效解，否则为 NPC 问题。

考虑如何将点覆盖集与割建立联系。对于一个点，如果割集中存在，那么说明点覆盖集中选择该点，同时在原图中与该点相连的点应不被割才符合题意，否则该边不存在任何点覆盖。

所以，网络流中的原图的边不能被割掉，故边权均为正无穷。不过，点是可以被割掉的，所以源点流向二分图一侧的每一个点，边权为该点的权值。从二分图的另一侧流向汇点，边权为该点的权值。（下图为示例）

不难发现，这样建立边权与原问题是等价的。考虑反证法，若存在一条边 $(u,v)$，点 $u$ 和点 $v$ 都没有被选择，那么说明源点连向 $u$ 的边与 $v$ 连向汇点的边均未被割，这说明残留网络中必然存在增广路（因为网络流中的 $(u,v)$ 边权为正无穷），与假设矛盾，证毕。

所以，在该网络流上跑最小割，即可求出原二分图的最小点全覆盖集。

代码 Code

#include 
#define fi first
#define se second
#define int long long

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

const int N = 点数, M = 边数;

int n, m, s, t;
int h[N], e[M], ne[M], f[M], idx;
int d[N], cur[N], st[N];

void add(int a, int b, int c) {
	e[idx] = b, ne[idx] = h[a], f[idx] = c, h[a] = idx ++;
	e[idx] = a, ne[idx] = h[b], f[idx] = 0, h[b] = idx ++;
}
bool bfs() {
	memset(d, -1, sizeof d);
	queue<int> q;
	q.emplace(s), d[s] = 0, cur[s] = h[s];
	while (q.size()) {
		int u = q.front();
		q.pop();

		for (int i = h[u]; ~i; i = ne[i]) {
			int v = e[i];
			if (d[v] == -1 && f[i]) {
				d[v] = d[u] + 1, cur[v] = h[v];
				if (v == t) return 1;
				q.emplace(v);
			}
		}
	}
	return 0;
}
int find(int u, int lim) {
	if (u == t) return lim;

	int flow = 0;
	for (int i = cur[u]; ~i && flow < lim; i = ne[i]) {
		cur[u] = i;
		int v = e[i];
		if (d[v] == d[u] + 1 && f[i]) {
			int tmp = find(v, min(lim - flow, f[i]));
			if (!tmp) d[v] = -1;
			f[i] -= tmp, f[i ^ 1] += tmp, flow += tmp;
		}
	}
	return flow;
}
int dinic() {
	int res = 0, flow;
	while (bfs()) while (flow = find(s, 1e18)) res += flow;
	return res;
}
void dfs(int u) {
	st[u] = 1;
	for (int i = h[u]; ~i; i = ne[i]) {
		int v = e[i];
		if (!st[v] && f[i]) dfs(v);
	}
}

signed main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	memset(h, -1, sizeof h);
	cin >> n >> m;

	s = 0, t = 2 * n + 1;
	int w;
	for (int i = 1; i <= n; i ++)
		cin >> w, add(s, i, w);
	for (int i = n + 1; i <= n * 2; i ++)
		cin >> w, add(i, t, w);
	while (m -- ) {
		int a, b;
		cin >> a >> b;
		add(a, b + n, 1e18);
	}

	cout << dinic() << endl;
    
    return 0;
}

习题

POJ2125 - Destroying The Graph

最大权独立集

引入 Introduction

独立集指对于图 $G(V,E)$，选出点集 $V^{\prime }$，使得对于 $V^{\prime }$ 中的任意 $2$ 个点，$2$ 点间都不存在一条边。

最大权独立集指对于所有独立集中点的权值和最大的独立集为最大权独立集。

主算法 Main Algorithm

最大权独立集 = 所有点权和 - 最小权点覆盖集

证明：

对于任意的点覆盖集 $V_1$，$V_1$ 在 $V$ 中的补集 $V_2$ 恒为独立集。

证明：反证法。若不是独立集，说明存在边 $(u,v)$ 使得 $u,v\in V_2$，那么由于 $V_2$ 为 $V_1$ 的补集，所以 $u,v\notin V_1$，故 $V_1$ 不是点覆盖集。与假设矛盾，证毕。

所以，$\sum _{i\in V_1}{w}_i+\sum _{i\in V_2}{w}_i=\sum _{i=1}^n{w}_i$。

故，当前项（最小权点覆盖集）取最小时，后项（最大权独立集）取最大。

综上所述，只需要沿用最小权点覆盖集的求解方法，并用总和减去其权值即可。

代码 Code

#include 
#define fi first
#define se second
#define int long long

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

const int N = 点数, M = 边数;

int n, m, s, t;
int h[N], e[M], ne[M], f[M], idx;
int d[N], cur[N], st[N];

void add(int a, int b, int c) {
	e[idx] = b, ne[idx] = h[a], f[idx] = c, h[a] = idx ++;
	e[idx] = a, ne[idx] = h[b], f[idx] = 0, h[b] = idx ++;
}
bool bfs() {
	memset(d, -1, sizeof d);
	queue<int> q;
	q.emplace(s), d[s] = 0, cur[s] = h[s];
	while (q.size()) {
		int u = q.front();
		q.pop();

		for (int i = h[u]; ~i; i = ne[i]) {
			int v = e[i];
			if (d[v] == -1 && f[i]) {
				d[v] = d[u] + 1, cur[v] = h[v];
				if (v == t) return 1;
				q.emplace(v);
			}
		}
	}
	return 0;
}
int find(int u, int lim) {
	if (u == t) return lim;

	int flow = 0;
	for (int i = cur[u]; ~i && flow < lim; i = ne[i]) {
		cur[u] = i;
		int v = e[i];
		if (d[v] == d[u] + 1 && f[i]) {
			int tmp = find(v, min(lim - flow, f[i]));
			if (!tmp) d[v] = -1;
			f[i] -= tmp, f[i ^ 1] += tmp, flow += tmp;
		}
	}
	return flow;
}
int dinic() {
	int res = 0, flow;
	while (bfs()) while (flow = find(s, 1e18)) res += flow;
	return res;
}
void dfs(int u) {
	st[u] = 1;
	for (int i = h[u]; ~i; i = ne[i]) {
		int v = e[i];
		if (!st[v] && f[i]) dfs(v);
	}
}

signed main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	memset(h, -1, sizeof h);
	cin >> n >> m;

	s = 0, t = 2 * n + 1;
	int w, tot = 0;
	for (int i = 1; i <= n; i ++)
		cin >> w, add(s, i, w), tot += w;
	for (int i = n + 1; i <= n * 2; i ++)
		cin >> w, add(i, t, w), tot += w;
	while (m -- ) {
		int a, b;
		cin >> a >> b;
		add(a, b + n, 1e18);
	}

	cout << tot - dinic() << endl;
    
    return 0;
}

习题

1. P4474 王者之剑
2. ABC354 G - Select Strings