Mirage_Insane

Mirage_Insane

关注
发信
关注(28)粉丝(399)

【网络流】总结

一、定义

设

显然，如果图中存在增广路，我们可以让一股流量沿着这条增广路从源点流到汇点。

那么 EK 算法的核心便是：利用

想一想为什么 EK 的效率不如 dinic。

因为 EK 算法找到一条增广路就迫不及待地进行了更新。

那么 dinic 就在它的基础上一次性寻找了多条增广路，再统一进行更新。

如何实现？

对于一个节点

还是以上述模板题目为例给一份代码：

Code:

#include<bits/stdc++.h>
using namespace std;
#define SF scanf
#define PF printf
#define int long long
struct Edge {
	int to, next, w;
}edge[200005];
int head[200005], cnt = 1, d[200005], now[200005]; //now数组就是当前弧优化的数组
void add(int u, int v, int w) {
	edge[++cnt].to = v;
	edge[cnt].next = head[u];
	edge[cnt].w = w;
	head[u] = cnt;
}
bool bfs(int s, int t) {
	queue<int> q;
	q.push(s);
	memset(d, 0, sizeof(d));
	d[s] = 1, now[s] = head[s];
	while(!q.empty()) {
		int tmp = q.front();
		q.pop();
		for(int i = head[tmp]; i; i = edge[i].next) {
			int to = edge[i].to;
			if(d[to] || edge[i].w <= 0) continue;
			d[to] = d[tmp] + 1;
			now[to] = head[to];
			q.push(to);
			if(to == t) return true;
		}
	}
	return false;
}
int dinic(int x, int t, int flow) {
	if(x == t) return flow;
	int rest = flow;
	for(int i = now[x]; i && rest; i = edge[i].next) {
		int to = edge[i].to;
		now[x] = i;
		if(d[to] != d[x] + 1 || edge[i].w <= 0) continue;
		int k = dinic(to, t, min(rest, edge[i].w));
		if(k == 0) d[to] = 0;
		edge[i].w -= k;
		edge[i ^ 1].w += k;
		rest -= k;
	}
	return flow - rest;
}
int work(int s, int t) {
	int ans = 0, delta;
	while(bfs(s, t)) {
		while(delta = dinic(s, t, INT_MAX)) ans += delta;
	}
	return ans;
}
signed main() {
	int n, m, s, t;
	SF("%lld%lld%d%lld", &n, &m, &s, &t);
	for(int i = 1; i <= m; i++) {
		int u, v, w;
		SF("%lld%lld%lld", &u, &v, &w);
		add(u, v, w), add(v, u, 0);
	}
	PF("%lld", work(s, t));
	return 0;
}

三、最小割

1、定义

把一张网络中的所有点分为 2 个点集，设其为 这里不再详细证明了，毕竟这玩意儿有点东西。

Code:

去上面看吧。

四、费用流

1、定义

在网络中的每条边上加上费用，设其为 SPFA 来求解。

为什么要用这玩意儿而不用复杂度更加稳定的 Dijkstra 呢？

因为图中有可能存在负环。

当然，存在负环时也是可以跑网络流的，只不过需要涉及到消圈算法，这里先不考虑。

首先我们要把费用当成权值跑一遍 SPFA，拿到到达每个点 因此就先放结论。以后有机会再来详细聊聊。现阶段就先记结论吧。

六、例题

1、奶牛食品

传送门

Algorithm：最大流。

基本上算是最大流的板子题。

介绍一种重要思路：拆点。

拆点

我们要明白拆点的意义究竟何在？

其实拆点就是将点权转化为边权。

拿此题讲，每只奶牛的贡献最多为 1。但它喜欢的食品和饮料不止 1 种。

如果直接用食品连接奶牛，奶牛连接饮料的话，它造成的贡献可能就不为 1 了。

因此，我们应该将奶牛 \(i\) 拆成 \(i_x\) 和 \(i_y\) 。一个用来表示是否得到喜欢的食品，另一个则表示是否得到喜欢的饮料。

做法显然了，超级源点 \(s\) 向第 \(f\) 个食品连接容量为 1 的边，第 \(d\) 个饮料向超级汇点 \(t\) 连接容量为 1 的边。

如果第 \(i\) 只奶牛喜欢第 \(f\) 个食品，就从 \(f\) 向 \(i_x\) 连一条容量为 1 的边。

如果第 \(i\) 只奶牛喜欢第 \(d\) 个饮料，就从 \(i_y\) 向 \(d\) 连一条容量为 1 的边。

当然，每个 \(i_x\) 也要向 \(i_y\) 连一条容量为 1 的边。上面说过每只奶牛的贡献最多为 1，因此容量为 1。

建图Code:

/*
第i个点：i -> max = n 
第i个吃: n + i -> max = n + lena
第i个喝：n + lena + i -> max = n + lena + lenb
第i个虚点： n + lena + lenb + i -> max = n + lena + lenb + n 
*/
int s = 0, t = 2 * n + lena + lenb + 1;
for(int i = 1; i <= n; i++) {
	int len1, len2, x;
	SF("%d%d", &len1, &len2);
	for(int j = 1; j <= len1; j++) {
		SF("%d", &x);
		add(n + x, i, 1), add(i, n + x, 0);		
	}
	for(int j = 1; j <= len2; j++) {
		SF("%d", &x);
		add(n + lena + lenb + i, n + lena + x, 1), add(n + lena + x, n + lena + lenb + i, 0);
	}
	add(i, n + lena + lenb + i, 1), add(n + lena + lenb + i, i, 0);
}
for(int i = 1; i <= lena; i++) add(s, n + i, 1), add(n + i, s, 0);
for(int i = 1; i <= lenb; i++) add(n + lena + i, t, 1), add(t, n + lena + i, 0);

2、猪

传送门

Algorithm：最大流。

有难度。

设第 \(i\) 个猪舍中有 \(a_i\) 头猪。

对每个猪舍 \(x\) 分类讨论。

  1. 该猪舍第一次被顾客 \(i\) 打开。

    这时可以从源点 \(s\) 向 \(i\) 连一条容量为 \(a_x\) 的边。表示第 \(i\) 个顾客最多从该猪舍买走 \(a_x\) 头猪。

  2. 该猪舍在被顾客 \(i\) 打开前已经被打开过。

    这时猪舍中的猪未知，怎么办呢？

    我们设上一位打开该猪舍的顾客为 \(last_x\) 。

    对 \(last_x\) 打开过的所有猪舍，我们都可以对里面的猪随意操作。

    可以理解为，\(last_x\) 和 \(i\) 是好朋友，\(last_x\) 担心自己买完猪后 \(i\) 不够买了，于是把自己能买的猪都买了，在 \(i\) 来的时候送给他了。

    所以我们从 \(last_x\) 向 \(i\) 连接一条容量为无限的边，表示 \(last_x\) 可以送给 \(i\) 无限多的猪以至于可满足 \(i\) 的需求。

    这样一来，问题就解决了。

当然，如果顾客 \(i\) 计划买 \(x_i\) 头猪，就从 \(i\) 向汇点 \(t\) 连接一条容量为 \(x_i\) 的边。表示他买的猪的数量。

至此，本题结束。

建图Code:

s = 0, t = n + 1;
for(int i = 1; i <= m; i++) SF("%d", &a[i]);
for(int i = 1; i <= n; i++) {
	int len, x;
	SF("%d", &len);
	for(int j = 1; j <= len; j++) {
		SF("%d", &x);
		if(last[x] == 0) {
			last[x] = i;
			add(s, i, a[x]), add(i, s, 0);
		}  
		else add(last[x], i, 0x3f3f3f3f), add(i, last[x], 0), last[x] = i;
	}
	SF("%d", &x);
	add(i, t, x), add(t, i, 0);
}

3、蜥蜴

传送门

Algorithm：最大流。

思路倒不难，调试起来有些困难。

在第一张图中，设第 \(i\) 行，第 \(j\) 列的石柱最多能够被跳 \(w_{i, j}\) 次。为了方便，赋予它一个编号 \(k_{i, j}\) 。

显然，根据上面拆点的思想，这里需要点权转边权。因此将第 \(i\) 行第 \(j\) 列的石柱拆为 \(k_{i, j, x}\) 和 \(k_{i, j, y}\) ，它们间边权即为 \(w_{i, j}\) 。

在第二张图中，如果第 \(i\) 行，第 \(j\) 列上有蜥蜴，就从源点 \(s\) 向 \(k_{i, j, x}\) 连接一条容量为 1 的边。再进一步，如果这只蜥蜴可以直接跳出图外，就从 \(k_{i, j, y}\) 向汇点 \(t\) 连接一条容量为 1 的边。

接下来枚举任意两块石柱。第一块在第 \(i\) 行，第 \(j\) 列，第二块在第 \(l\) 行，第 \(r\) 列。如果他们间的距离足以让蜥蜴跳过，就在 \(k_{i, j, y}\) 和 \(k_{l, r, x}\) 间连接一条容量为 1 的边，表示从第一块跳到第二块。同样，在 \(k_{l, r, x}\) 和 \(k_{i, j, y}\) 间连接一条容量为 1 的边，表示从第二块跳到第一块。

到这里，建图就结束了。

建图Code:

SF("%d%d%d", &n, &m, &Max);
for(int i = 1; i <= n; i++) {
	for(int j = 1; j <= m; j++) {
		char c;
		cin >> c;
		if(c != '0') x[++len] = i, y[len] = j, w[len] = c - '0', k[i][j] = len;
	}
}
s = 0, t = 2 * len + 1;
for(int i = 1; i <= n; i++) {
	for(int j = 1; j <= m; j++) {
		char c;
		cin >> c;
		if(c == 'L') {
			sum++;
			add(s, k[i][j], 1), add(k[i][j], s, 0);
		}
	}
}
for(int i = 1; i <= len; i++) {
	add(i, i + len, w[i]), add(i + len, i, 0);
	for(int j = i + 1; j <= len; j++) {
		if(get_dis(x[i], y[i], x[j], y[j]) <= Max * Max) add(i + len, j, 0x3f3f3f3f), add(j, i + len, 0), add(j + len, i, 0x3f3f3f3f), add(i, j + len, 0);
	}
}
for(int i = 1; i <= len; i++) {
	if(x[i] <= Max || y[i] <= Max || x[i] + Max > n || y[i] + Max > m) add(i + len, t, 0x3f3f3f3f), add(t, i + len, 0);
}

4、有线电视网络

传送门

Algorithm：最小割

显然，割掉一个点，所有与这个点的相连的边都会一并被删掉。

所以将第 \(i\) 个点拆为 \(i_x\) 和 \(i_y\) 。

如果 \(u\) 和 \(v\) 之间有一条无向边，就从 \(u_y\) 向 \(v_x\) 间连一条容量为无限的边。同时也从 \(v_y\) 向 \(u_x\) 间连一条容量为无限的边。

为什么是无限？

因为题目中不让删边，容量设为无限那么最小割一定不会割掉它。

同时，对于任意一个非源点并且非汇点的点 \(i\) ，从 \(i_x\) 向 \(i_y\) 间连一条容量为 1 的边。表示删除该点需要 1 的代价。

为什么要排掉源汇点呢？

如果不排掉的话，最小割就可能会选择割掉 \(s_x\) 和 \(s_y\) 间的边或 \(t_x\) 和 \(t_y\) 间的边。此时满足最小割的定义，会直接返回。但实际上割掉源汇点后图可能还是联通的。

所以干脆就不割，将 \(s_x\) 和 \(s_y\) 间的边和 \(t_x\) 和 \(t_y\) 间的边的容量设为无限。

这样就需要枚举每个源汇点来去最小值才能保证正确性了。

难度不大，能够帮助我们进一步理解拆点的意义。

建图简单，输入很恶心，只给输入的代码。

建图Code:

for(int i = 1; i <= m; i++) {
	SF("%s", c + 1);
	int lenc = strlen(c + 1);
	bool flag = false;
	for(int j = 1; j <= lenc; j++) {
		int sum = 0, u, v;
		bool F = false;
		while(c[j] >= '0' && c[j] <= '9') {
			F = true;
			sum = (sum << 3) + (sum << 1) + (c[j] ^ 48);
			j++;
		}
		if(!F) continue;
		sum++;
		if(!flag) a[i] = sum, flag = true;
		else b[i] = sum;
	}
}

5、 狼和羊的故事

传送门

Algorithm：最小割

为了方便，将所有狼的坐标存储在 \(id1\) 里，羊的坐标存储在 \(id2\) 里，空点的坐标存储在 \(id3\) 里。它们都是 pair 类型的。

对于图中的第 \(i\) 行，第 \(j\) 列，赋予它一个编号 \(num_{i, j}\)。

题目描述说空点不是任何一只动物的领地，其实意思是狼可以通过空点来进攻羊。

所以狼有两种方式进攻羊：

  1. 相邻的节点中就有羊，直接进攻。
  2. 相邻的节点中有空点，空点可以通过若干个空点与羊相邻，通过空点进攻。

因此该题建图的思路就出来了。

  1. 枚举第 \(i\) 只狼和第 \(j\) 个空点。如果它们间的曼哈顿距离为 1，则从 \(num_{id1_i.first, id1_i.second}\) 向 \(num_{id3_j.first, id3_j.second}\) 连接一条容量为 1 的边，表示第 \(i\) 只狼可以到达第 \(j\) 个空点。
  2. 枚举第 \(i\) 个空点和第 \(j\) 只羊。如果它们间的曼哈顿距离为 1，则从 \(num_{id3_i.first, id3_i.second}\) 向 \(num_{id2_j.first, id2_j.second}\) 连接一条容量为 1 的边，表示第 \(i\) 个空点可以到达第 \(j\) 只羊。
  3. 枚举任意两个空点 \(i\) 和 \(j\)。如果它们间的曼哈顿距离为 1，则从 \(num_{id3_i.first, id3_i.second}\) 向 \(num_{id3_j.first, id3_j.second}\) 连接一条容量为 1 的边，表示第 \(i\) 个空点可以到达第 \(j\) 个空点。
  4. 枚举第 \(i\) 只狼和第 \(j\) 只羊。如果它们间的曼哈顿距离为 1，则从 \(num_{id1_i.first, id1_i.second}\) 向 \(num_{id2_j.first, id2_j.second}\) 连接一条容量为 1 的边，表示在它们之间加一个单位距离的栅栏。

源点和汇点怎么处理呢？

枚举第 \(i\) 只狼，从源点 \(s\) 向它连一条容量为无限的边。

枚举第 \(i\) 只狼，从它向汇点 \(t\) 连一条容量为无限的边。

你不可能将任何一只狼或者任何一只羊莫名删掉，因此容量为无限。

跑一便最小割即可。

建图Code:

SF("%d%d", &n, &m);
for(int i = 1; i <= n; i++) {
	for(int j = 1; j <= m; j++) {
		SF("%d", &x);
		num[i][j] = ++sum;
		if(x == 1) id1[++len1].first = i, id1[len1].second = j;
		else if(x == 2) id2[++len2].first = i, id2[len2].second = j;
		else id3[++len3].first = i, id3[len3].second = j;
	}
}
int S = 0, T = sum + 1;
for(int i = 1; i <= len1; i++) add(S, num[id1[i].first][id1[i].second], 0x3f3f3f3f), add(num[id1[i].first][id1[i].second], S, 0);
for(int i = 1; i <= len2; i++) add(num[id2[i].first][id2[i].second], T, 0x3f3f3f3f), add(T, num[id2[i].first][id2[i].second], 0);
for(int i = 1; i <= len1; i++) {
	for(int j = 1; j <= len3; j++) {
		if(abs(id1[i].first - id3[j].first) + abs(id1[i].second - id3[j].second) == 1) add(num[id1[i].first][id1[i].second], num[id3[j].first][id3[j].second], 1), add(num[id3[j].first][id3[j].second], num[id1[i].first][id1[i].second], 0);
	}
}
for(int i = 1; i <= len3; i++) {
	for(int j = 1; j <= len2; j++) {
		if(abs(id3[i].first - id2[j].first) + abs(id3[i].second - id2[j].second) == 1) add(num[id3[i].first][id3[i].second], num[id2[j].first][id2[j].second], 1), add(num[id2[j].first][id2[j].second], num[id3[i].first][id3[i].second], 0);
	}
}
for(int i = 1; i <= len3; i++) {
	for(int j = 1; j <= len3; j++) {
		if(i == j) continue;
		if(abs(id3[i].first - id3[j].first) + abs(id3[i].second - id3[j].second) == 1) add(num[id3[i].first][id3[i].second], num[id3[j].first][id3[j].second], 1), add(num[id3[j].first][id3[j].second], num[id3[i].first][id3[i].second], 0);
	}
}
for(int i = 1; i <= len1; i++) {
	for(int j = 1; j <= len2; j++) {
		if(abs(id1[i].first - id2[j].first) + abs(id1[i].second - id2[j].second) == 1) add(num[id1[i].first][id1[i].second], num[id2[j].first][id2[j].second], 1), add(num[id2[j].first][id2[j].second], num[id1[i].first][id1[i].second], 0);
	}
}

6、航空路线问题

传送门

Algorithm：费用流

初看此题似乎看不出来得用费用流。没关系，我们先站在最大流的角度思考一下问题。

需要我们找到 2 条路线：一条要从 \(s\) 到 \(t\) ，另一条要从 \(t\) 到 \(s\) ，并且往返途中每座城市只能经过一次。不难想到拆点。对于点 \(i\) ，拆成入点 \(in_i\) 和出点 \(out_i\) 。从 \(in_i\) 向 \(out_i\) 连接一条容量为 1 的边，表示该点最多经过一次。特别地，\(in_s\) 和 \(out_s\) 之间的容量为 2，\(in_t\) 和 \(out_t\) 之间的容量也为 2。对于两个点 \(u\) 和 \(v\) ，如果它们之间有路径，则从 \(out_u\) 向 \(in_v\) 连接一条容量为无限的边。

做题经验告诉我们，此题可以转化成从 \(s\) 到 \(t\) 找到 2 条不同的路径，再输出答案即可。

当然，如果最大流不为 2，说明 \(s\) 和 \(t\) 不连通，输出无解。

至此，本题结束。了吗？

事实告诉我们，如果单单只跑最大流并判断无解，只能拿到 \(27pts\) ，为什么会错呢？

因为我们要保证路过的城市尽可能多，而不是仅仅找出 2 条路径。

这就是此题需要费用流的原因。

对于每一个点 \(i\) ，在 \(in_i\) 和 \(out_i\) 之间的边上加上 1 点费用，表示流经了一座城市。其它的所有边费用均为 0，再跑一遍最大费用最大流就解决了此题。

补：将所有城市的名字用 \(map\) 映射成数字后比较好处理。

建图Code:

S = 0, T = 2 * n + 1;
for(int i = 1; i <= n; i++) {
	cin >> u;
	mp[u] = ++_, Mp[_] = u; //map映射
	if(i == 1) add(S, mp[u], 2, 0), add(mp[u], S, 0, 0), add(mp[u], mp[u] + n, 2, -1), add(mp[u] + n, mp[u], 0, 1);
	else if(i == n) add(mp[u], T, 2, 0), add(T, mp[u], 0, 0), add(mp[u], mp[u] + n, 2, -1), add(mp[u] + n, mp[u], 0, 1);
	else add(mp[u], mp[u] + n, 1, -1), add(mp[u] + n, mp[u], 0, 1);
} //将每个费用取反后跑最小费用，跑出来的答案取反就是最大费用了
for(int i = 1; i <= m; i++) {
	cin >> u >> v;
	add(mp[u] + n, mp[v], 0x3f3f3f3f, 0), add(mp[v], mp[u] + n, 0, 0);
}

给一下我习惯用的拉答案的方式供参考：

void get_res(int x) {
	if(x == T) return;
	res[len][++res[len][0]] = (x > n ? x - n : x);
	for(int i = head[x]; i; i = edge[i].next) {
		int to = edge[i].to;
		if(i & 1) continue; //链式前向星的性质
		if(edge[i ^ 1].c) {
			edge[i ^ 1].c--;
			get_res(to);
			break;
		}
	}
}
-----------------------------------------分割线-------------------------------------------
for(int i = head[S]; i; i = edge[i].next) {
	if(i & 1) continue; 
	while(edge[i ^ 1].c) {
		edge[i ^ 1].c--;
		len++;
		get_res(edge[i].to);
	}
}
int len1 = unique(res[0] + 1, res[0] + 1 + res[0][0]) - res[0] - 1;
int len2 = unique(res[1] + 1, res[1] + 1 + res[1][0]) - res[1] - 1;
cout << len1 + len2 - 2 << endl;
for(int i = 1; i < len1; i++) cout << Mp[res[0][i]] << endl;
for(int i = len2; i; i--) cout << Mp[res[1][i]] << endl;

这种方式每次只能拉 1 点流量，较为耗时，但已经足以面对绝大多数情况了。

7、清理雪道

传送门

Algorithm：上下界网络流

通过读题，不难发现每条边都至少要经过一次来打扫雪道，因此每条边的容量的下界为 1，上界为无限，跑一遍无源汇上下界最小流即可。

具体地说，先建立超级源点 \(s\) 和超级汇点 \(t\)，\(s\) 连向所有入度为 0 的点，下界为 0，上界为无限；所以出度为 0 的点连向 \(t\) ，下界为 0，上界为无限。跑一遍有源汇上下界最小流即答案。

建图Code:

不放了，见上面的模板，改动不大。

完结撒花~~~

08-13 07:26
Powered by LMLPHP ©2024 Mirage_Insane 0.008351