语言漩涡

thirtiseven 的博客

0%

平面图最小链覆盖 POI2002 Skiers

Posted on Edited on

题意

给一个图，它是个DAG（有向无环图），它是个平面图，它有一个起点和一个终点，求最小的从起点到终点的路径数量，使得存在一组这么多路径可以覆盖这个图的每一条边。

输入输出

输入一个图，输出一个数，具体不说了。

nar

样例长这样，它应该输出 8.

解法

由于这个题的（没翻译的）题目背景，我们把这种有一个起点和一个终点的平面DAG叫做滑雪图。

定义滑雪图的对偶图，把滑雪图的边当作对偶图的点，如果两个滑雪图的边连接着同一个点，则对应的两个对偶图的点就连边。我们把滑雪图叫做 ，对偶图叫做 。（注意，图论里真的对偶图不是这样的，真的对偶图是线图。）

定义 关系，如果在 中存在一个从 到 的路径，那么 。复习一下离散数学，我们发现这种关系是自反、非对称、传递的，所以这是一个偏序关系。

如果一个集合里存在一个偏序关系，那我们叫这个集合偏序集。把对偶图里所有的点扔到一个集合里，那么这个集合就是一个偏序集。

在一个偏序集 中，如果 ，那么我们把集合 称为一个链。如果一个链不能再扩展，那么这个链称为最长链。在这个题里，一个最长链就是一条从起点到终点的路线。

链也有一个对偶概念。集合 称为一个反链，如果任意集合中任意两个元素都不满足偏序关系 。同样的，如果一个反链不能扩充，它就被称为最长反链。

定义 为集合 的一个子集族。如果这些子集的并集等于 ，那么这个子集族被称为 A 的一个覆盖。在这个题里，如果一组路线能覆盖到原图的每一条边，那么这组路线就是一个覆盖。

于是我们可以把这道题转化为：在滑雪图的对偶图的偏序集里面求最小的最长链族（它本质上是个子集），使得这个子集族成为集合的一个覆盖。简称：最小链覆盖。

值得一提的是，DAG的最小链覆盖存在一个拆点+二分图匹配的通用做法。将原图的每个点 拆开为 和 。如果 A 和 B 之间有一条边，那么就连接 和 。这样建成的新图是一个二分图，最小链覆盖的个数就是原图的节点数 - 二分图最大匹配数。因为一开始每个点都是独立的为一条路径，总共有 n 条不相交路径。我们每次在二分图里找一条匹配边就相当于把两条路径合成了一条路径，也就相当于路径数减少了1。所以找到了几条匹配边，路径数就减少了多少。所以有最小路径覆盖=原图的结点数-新图的最大匹配数。但是复杂度很高，不能接受，考虑别的做法。

要求最小链覆盖，我们可以用 Dilworth 定理。Dilworth 定理说：偏序集的最长反链长度等于最小链覆盖个数。感性理解一下：同一条链的元素在最长反链中至多会出现一次，要最小化最小链覆盖的个数，就要让最长反链中的每一个元素在每一条链中恰好出现一次。这个东西可以用第二数学归纳法证明（证明没怎么看懂，呜呜

于是问题转化成了求对偶图的最长反链。解决这个问题需要用到这个图是平面图的性质。由于原图是一个平面图，那么平面就会被这个图分割成不同的部分，每个部分称为一个面。那么在对偶图中，最长反链就可以直观地表示为将一组彼此左右相邻的面分开的边。也就是说，如果我们把这个平面图水平切开，切断的最多的边的条数就是最长反链的长度。我们把面用大写字母标号，看一下这个图。

Screen Shot 2021-03-03 at 3.26.55 PM

尝试把这种思路转化为算法。先对着滑雪图建面的图。让每一条边从西到东地连接它们连接的两个面。注意到如果直接这么连是可能有重边的，如果出现了重边，就随便取一条边。建完图之后样例长这个样子。

Screen Shot 2021-03-03 at 9.04.42 PM

于是问题转化为了求这个图中的最长路径。最终答案就是这个值加2，因为两侧的两个面外侧还分别有一条边没有算进去。DAG最长路径是个经典问题，解法是拓扑排序+DP，复杂度是O(n)的。而由于欧拉定理，平面图中面的个数也是O(n)的，所以建面图是 O(n) 的，所以最终的总复杂度也是 O(n) 的。

实际编程中，不需要显式地求出面图也不需要显示地跑拓扑排序，只需要把dp数组记录在边上，一个一个找到每一个面，更新答案就可以了。使用一个pre[n]数组记录每个点最近一次是从哪条边来的。找到每一个面的方法是dfs，如果访问到以访问过的点，说明当前点是一个面的最低点，按pre数组向上回溯（此时pre数组记录的是上次到达这个点的边，即面的左侧边），直到发现一个有未处理右侧边的点，把它标记为当前面的最高点。然后再更新pre数组，按更新后的pre数组向上回溯，直到回到标记过后的最高点。最终答案为所有边上dp数组的最大值。由于每个点被访问的次数是常数次的，所以回溯操作对复杂度没有影响。具体可以看代码的注释。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <iostream>
#include <vector>
#include <algorithm>

const int maxn = 5005;

struct Edge{
	int from, to;
};

std::vector<Edge> e;
std::vector<int> g[maxn];
int dp[300000];

void addedge(int u, int v){
	e.push_back((Edge){u,v});
	g[u].push_back(e.size()-1);
}

int pre[maxn], vis[maxn];
//pre: 当前处理过的边中最后一条指向 i 的边的标号
//vis: 0 未被访问，1 当前访问节点或其祖先节点，2 没有未处理的右侧的边

std::pair<int,int> back(int u) {
//	std::cerr << "BACK " << u << '\n';
	int ans = 0;
//	std::cerr << "ans: " << ans << " dp[pre[u]]:" << dp[pre[u]] << " pre[u]: " << pre[u] << " u: " << u << '\n';
	do {
		ans = std::max(ans, dp[pre[u]]);
		u = e[pre[u]].from;
//		std::cerr << "ans: " << ans << " dp[pre[u]]:" << dp[pre[u]] << " pre[u]: " << pre[u] << " u: " << u << '\n';
	} while(vis[u] != 1); //找到一个有未处理右侧边的点，把它作为面的最高点
	return std::make_pair(u, ans+1);
}

void refresh(int u, std::pair<int,int> ans) {
//	std::cerr << "REFRESH " << u << " ans:" << ans.first << ' ' << ans.second << '\n';
//	std::cerr << "dp[pre[u]]:" << dp[pre[u]] << " pre[u]: " << pre[u] << " u: " << u << '\n';
	do {
		dp[pre[u]] = ans.second;
		u = e[pre[u]].from;
//		std::cerr << "dp[pre[u]]:" << dp[pre[u]] << " pre[u]: " << pre[u] << " u: " << u << '\n';
	} while(u != ans.first);
}

void dfs(int u) {
	vis[u] = 1;
//	std::cerr << "vis[" << u << "]: 1\n";
	for (int i = 0; i < g[u].size(); i++){
		int v = e[g[u][i]].to;
		dp[g[u][i]] = 1;
		if (!vis[v]) {
			pre[v] = g[u][i];
			dfs(v);
		} else { //如果发现访问过，说明有两条路线相遇了
			std::pair<int,int> ans = back(v); //找到左侧边，更新答案，把答案+1
			pre[v] = g[u][i];
			refresh(v, ans);	//把新答案记录在边上
		}
	}
	vis[u] = 2; 
//	std::cerr << "vis[" << u << "]: 2\n";
}

int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0); 
	int n;
	std::cin >> n;
	for(int i = 1; i < n; i++){
		int k;
		std::cin >> k;
		int v;
		for(int j = 1; j <= k; j++) { 
			std::cin >> v;
			addedge(i, v);
		}
	}
	dfs(1);
	int ans=0;
	for (int i = 0; i < e.size(); i++)
	ans = std::max(ans, dp[i]);
	std::cout << ans << '\n';
}

吐槽

想法很美好，现实是我不知道怎么找一个平面图的所有面。然后在网上搜到了唯一一个题解... 网友寥寥几句指点了一下，完全没看懂，但是代码写得还是很牛逼的...

那个对偶图还有偏序关系什么的就是为了引出 Dilworth 定理，没有别的用处（

以及 Code Jam 提醒小助手又上线了，如果有人看到这里，不如顺便去报个 Google Code Jam，惊险刺激非常狂野，月底资格赛了（