首页 > 其他分享 >「网络流浅谈」最小割的模型

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

时间：2024-05-21 22:07:29浏览次数：37  
标签：浅谈 idx int sum flow 最小 ne 模型 cur

最大权闭合子图

引入 Introduction

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

最大权闭合子图无非就是对于所有的闭合子图 \(G\) 中 \(\sum_{u\in V} w_u\) 最大的闭合子图。

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

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

主算法 Main Algorithm

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

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

对于割 \([S,T]\)，\(c(S,T)=\sum_{(u,v)\in E,u\in S,v\in T}c(u,v)\)，由于中间的边权均为 \(+\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 <bits/stdc++.h>
#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'=(V',E')\)，满足 \(\forall (u,v)\in E', u\in V',v\in V'\)。对于所有满足条件的子图 \(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,\bar V)}{2}\)。这样，就与割产生了关系。

继续推式子：\(g|V|-|E|=\sum_{u\in V}g-\frac{\sum_{u\in V}d_u-c(V,\bar V)}{2}=\sum_{u\in V}(g-\frac{d_u}{2})+\frac{c(V,\bar V)}{2}\)

为了使与最小割有单调关系，将割 \(c(V,\bar V)\) 的系数提出得 \(\frac{\sum_{u\in V}(2g-d_u)+c(V,\bar 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'(S,T)\) 与 \(|E|-g|V|\) 的关系。令 \(P=S-\{s\},P'=\bar P - \{t\}\)，则最小割的边集分为 \(4\) 种情况：\(P\rightarrow \{t\},\{s\}\rightarrow P',P\rightarrow P',\{s\}\rightarrow \{t\}\)。不过，最后一种边不存在舍去。

\[\begin{aligned} c'(S,T)=&\sum_{u\in P} (U+2g-d_u)+\sum_{v\in P'}U+\sum_{u\in P}\sum_{v\in P'}c(u,v)\\ =&\sum_{u\in P}(U+2g-d_u+\sum_{v\in P'}c(u,v))+\sum_{v\in P'}U\\ =&\sum_{u\in P}(U+2g-(d_u-\sum_{v\in P'}c(u,v)))+\sum_{v\in P'}U\\ =&\sum_{u\in P}(U+2g-\sum_{v\in P}c(u,v))+\sum_{v\in P'}U\leftarrow u\ 所有出边-向集合外边=向集合内边\\ =&\sum_{u\in P}2g-\sum_{u\in P}\sum_{v\in P}c(u,v)+\sum_{v\in P'}U+\sum_{v\in P}U\\ =&|P|2g+ 2|E|+U\cdot n\\ \end{aligned} \]

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

POJ3155 - Hard Life

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

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

#include <bits/stdc++.h>
#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 <bits/stdc++.h>
#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'\)，使得对于 \(V'\) 中的任意 \(2\) 个点，\(2\) 点间都不存在一条边。

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

主算法 Main Algorithm

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

证明：

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

证明：反证法。若不是独立集，说明存在边 \((u,v)\) 使得 \(u,v\in V_2\)，那么由于 \(V_2\) 为 \(V_1\) 的补集，所以 \(u,v\not\in 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 <bits/stdc++.h>
#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

标签：浅谈,idx,int,sum,flow,最小,ne,模型,cur
From： https://www.cnblogs.com/Tiny-konnyaku/p/18205050

相关文章

  • 互斥锁，IPC机制，队列，生产者消费者模型
    Ⅰ互斥锁【一】什么是互斥锁互斥锁其实就是一种锁。为当前进程或线程添加额外的限制限制当前时间段只能由当前进程使用，当前进程使用完成后才能其他进程继续使用其作用是保证在同一时刻只有一个线程在访问共享资源，从而避免多个线程同时读写数据造成的问题。互斥锁的基本原......
  • weblogic漏洞浅谈
    weblogic反序列化漏洞原理分析weblogic是oracle公司出品的applicationserver，用于本地和云端开发，集成，部署和大型分布式web应用，网络应用和数据库应用的Java应用服务器weblogicserver是一个基于JAVAEE架构的中间件，将java的动态功能和javaEnterprise标准的安全性引入大型网络应用......
  • CSP历年复赛题-P1029 [NOIP2001 普及组] 最大公约数和最小公倍数问题
    原题链接：https://www.luogu.com.cn/problem/P1029题意解读：已知x，y，求有多少对p、q，使得p、q的最大公约数为x，最小公倍数为y。解题思路：枚举法即可。枚举的对象：枚举p，且p必须是x的倍数，还有p<=yq的计算：q=x*y/p，q要存在，必须x*y%p==0，且gcd(p,q)==x100分代码：#include......
  • 模型选择
    模型选择采用敏捷软件开发过程模型。以下是选型的理由：1.需求变化频繁由于需求经常会发生变化，采用传统的瀑布模型容易导致开发滞后、项目延期等问题。而敏捷开发强调快速响应客户需求，能够更好地适应需求变化。2.开发周期较短高校社团管理系统是一个小型的项目，开发周期相对较短......
  • 3D学校模型：开启未来教育的全新篇章
    随着科技的飞速发展，教育领域也迎来了前所未有的变革。 3D学校模型：开启全新学习体验3D学校模型，是通过3D建模技术构建的学校立体模型。它不仅能还原学校的真实场景，还能实现多角度、全方位的展示，学生能身临其境地走进学校的每一个角落，感受不同教室的学习氛围，探索各种功能区域。这......
  • 鸿蒙HarmonyOS实战-Stage模型（卡片数据交互）
    ......
  • STAR模型
    “故事是人类的共同语言。”在管理中，故事的力量不容忽视。 如何讲好一个故事？试试STAR模型吧！   先设定情境（Situation），再明确任务（Task），然后描述行动（Action），最后展示结果（Result）。 这样的故事不仅生动有趣，更能展现你的能力和成就。 “故事是最有感染力的教育方式。” ......
  • ACE模型
    决策是管理的核心，但决策并不总是那么容易。 使用ACE模型，让你的决策更加高效和准确。 先评估（Assess）情况和选项，再选择（Choose）最佳方案，最后执行（Execute）决策。简单而直接，却能在关键时刻为你指明方向。 1. 评估：快速评估情况和可行选项为决策提供依据。 2. 选择：选择最......
  • 【Halcon】实现分离通道、创建矩形、获取灰度级、求最大最小均值、求大于某一灰度级的
    read_image(Image,'D:/image/123.jpg')rgb1_to_gray(Image,GrayImage)gen_rectangle1(Rectangle,100,100,200,200)rectangle1_domain(GrayImage,ImageReduced,100,100,200,200)crop_domain(ImageReduced,ImagePart)get_region_points(ImageP......
  • 生产者和消费者模型
    进程间通信（IPCinter-processcommunication）如何实现进程间通信将消息放入队列中，由另一个进程从另一个队列中取出这种通信方式是非阻塞的，发送进程不需要等待接收进程的相应就可执行multiprocessing有两种形式通信：队列、管道管道stdinstdoutstderr队列管道+......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99