【NOIP2018】旅行 (洛谷P5049 / P5022) O(nlogn)题解_洛谷旅行编程题讲解

阅读和学习本篇题解前，你应该掌握：

C++ STL stack、vector、queue、pair的基本用法；

递归、搜索和贪心思想。

        洛谷传送门 P5049

        此题可以先从数据范围入手，观察m的范围（m == n || m == n - 1）可知此题发生在一棵树或一棵基环树上。

目录

什么是基环树？

基本思路

60%做法

预处理

100%做法

找到环在哪里

对环上的点进行处理（重点）

断环后在树上求解 

 大功告成！

完整代码

大样例

---

---

什么是基环树？

        基环树又称 环套树 、 树套环 、 章鱼图。顾名思义，即由环和树组成的图，但特殊的是它只含有一个环，即一棵树再加一条边构造而成。对于这种图的处理，通常是找到合适的位置将环断开，使其转化为树进行处理。

       

将环断开后，我们有了一棵树。

那么如何在树上贪心？

---

基本思路

        根据题目对字典序更小的数学定义：

• 对于任意正整数 1 ≤ i < x，序列 A 的第 i 个元素  和序列 B 的第 i 个元素  相同。
• 序列 A 的第 x 个元素的值小于序列 B 的第 x 个元素的值。

        由此我们可以知道，对于相等长度的两个序列，若序列最后一位之前的所有元素均相同，则决定序列字典序大小的元素就是最后一位，换句话说，用递推的方式产生答案，每次都尽可能地令更小的元素排在序列靠前面的位置，就能够产生最优解。这就是解决这道题的贪心思路。

---

60%做法

        对于（m == n - 1）的情况，在树上按照子节点大小的顺序进行深搜，先搜编号较小的节点，然后输出即可。另外，DFS的入口，不难看出，一定是整个图中编号最小的点，即一号节点。

预处理

        由于要按照子节点大小进行排序，为了避免时间复杂度过高（O() 级别)，此处推荐使用vector进行图的储存。

以下是实现存边和深搜需要使用的存储空间：

const int maxn = (int)5e5 + 5;
bool vis[maxn];         //节点是否被遍历过
vector<int> ed[maxn];

        输入边的连接情况后得到了vector存储的邻接表（无向图存双向），接下来使用sort对所有点的子节点进行排序：

	scanf("%d %d", &n, &m);
	for (int i = 1; i <= m; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		ed[x].push_back(y);
		ed[y].push_back(x);
	}        //输入&存图，无向图存双向边
 
	for (int i = 1; i <= n; i++) {
		if (ed[i].size() > 1) {        //若（儿子数 >= 2）才有排序的必要
			sort(ed[i].begin(), ed[i].end());
		}
	}

        做好了这一步，就可以开始快乐地DFS了~

        同时可以在DFS的过程中输出答案。

void dfs(int x) {
	printf("%d ", x);
	vis[x] = 1;
	for (int i = 0; i < ed[x].size(); i++) {
		int y = ed[x][i];
		if (vis[y]) continue;
		dfs(y);
	}
	return;
}

至此，60%的做法就完成了。

---

100%做法

        将环断开，边数便减少了一条，即成为一棵树，届时做法同上。

那么如何找出要断开的边在哪里？

找到环在哪里

        我们知道，断开的边一定在环上，所以要先确定环的位置。我们可以从一号点开始在图上进行DFS，同时使用栈记录下来被遍历的路径，从叶子节点返回时出栈，这样不断搜索，直到再次遍历到已经在栈中的节点。此时，设栈中唯一被遍历过两次的节点为，则即为环的入口，从栈顶开始到第一次出现处的所有节点均为环上的节点。

以下是实现深搜和找环需要使用的存储空间：

const int maxn = (int)5e5 + 5;
int head;        //环的入口
int tail;        //环的最后一个节点
bool vis[maxn];  //节点是否在栈中
bool onrg[maxn]; //节点是否在环上
stack<int> v, r;    //v为遍历路径所在的栈，r为环上的所有节点

        接下来我们可以开始深搜找环了。注意这里的递归函数要定义成bool型，以此区分当前回溯的原因是找到了环还是找到了叶子结点。

bool findRing(int x, int fa) {
	if (vis[x]) {
		head = x;        //记录环的入口
		onrg[x] = 1;     //将节点标记为“在环上”，方便之后查询
		tail = v.top();  //记录环的出口
		while (v.top() != x) {
			onrg[v.top()] = 1;
			r.push(v.top());    //将搜索路径上属于环的点移入栈 r 中
			v.pop();     
		}
		return 1;       //找到了环，不需要再搜了，返回
	}
 
	vis[x] = true;
	v.push(x);
	for (int i = 0; i < ed[x].size(); i++) {
		if (ed[x][i] == fa) continue;
		if (findRing(ed[x][i], x)) return 1;    //若找到了环，返回，否则继续搜索
	}
	v.pop();
	vis[x] = 0;
	return 0;    //没能找到环，但这是叶子节点了，回溯后继续搜索
}

        好了，现在我们整理一下经过这一遍深搜以后，我们得到了哪些信息：

• 环的入口（深搜时环上第一个点）
• 环的出口（环上处于入口前的点）
• 哪些点在环上（onrg数组 和 栈 r 共同记录的内容）

        有了这些信息我们就可以在这些点之间进一步确定要断开的是哪条边了。

那么如何进一步确定断开的边？

对环上的点进行处理（重点）

        这一步需要对环上除了入口以外的所有节点进行处理，同时确定出要断开的边，为什么入口不需要呢？

        我们需要先比较从入口出发是向左更优还是向右更优，然后沿更优的方向进入环，所以入口不可能是断环时距离起点较近的节点。（见下图）

         那么我们就确定了在环上进行遍历的方向，即向第一个节点的编号较小的那个方向进行遍历，这里我们比较两个节点，并决定是否要翻转环的方向，若需要则使用队列辅助翻转。

queue<int> opq;
 
if (r.top() > tail) {        //此时r.top()是入口后的第一个节点，tail是入口前最后一个节点
	swap(r.top(), tail);
	while (!r.empty()) {
		opq.push(r.top());
		r.pop();
	}
	while (!opq.empty()) {
		r.push(opq.front());
		opq.pop();
	}
}

        确定好了方向就可以开始处理环上的信息了，我们需要对环上除了入口的每个点都处理出以下信息：

        通过处理出的以上信息，我们就可以确定断环的位置了。

        先说结论：

        设当前节点为 x，环上的下一个节点为 y，回溯后要遍历的第一个节点为 turn，当且仅当 y > turn && y == ed[x][ed[x].size() - 1]时，删去 x 和 y 之间的边。

         如图，按照上面的结论，我们选择 2 和 6 之间的边断开。

        接下来我们看一下这些信息具体是如何被处理出来的，以及处理出的信息是如何被用于判断条件是否满足的。

while (!r.empty()) {

int x = r.top();	r.pop();
 
if (ed[x][ed[x].size() - 1] > turn && ed[x][ed[x].size() - 1] == r.top()) {
	brk.first = x;
	brk.second = r.top();
	break;
} else {
	if (ed[x][ed[x].size() - 1] != r.top() && onrg[ed[x][ed[x].size() - 1]]) {
		if (ed[x][ed[x].size() - 2] > turn && ed[x][ed[x].size() - 2] == r.top()) {
			brk.first = x;
			brk.second = r.top();
			break;
		}
	}
}

        开门见山，我们直接判断当前节点 x 是否满足条件。若满足，则断开 x 和 r.top() 之间的边。值得注意的是，由于我们建的是双向边，所以有时候ed[x][ed[x].size() - 1]是一条指向上一节点的多余的边，这是会影响条件是否被满足的，所以我们还需要在下面多判断一层，以排除这条多余边的影响。

        如果条件仍未被满足，说明我们还没有找到要断开的边，那么我们继续沿着环进行遍历。

if (ed[x][ed[x].size() - 1] != r.top()) {
	if (ed[x].size() > 2)   //r.top()和上一个节点分别是x的两个子节点，若还有子节点则执行
		for (int i = 0; i < ed[x].size(); i++) {
			if (ed[x][i] == r.top()) {
				if (onrg[ed[x][i + 1]]) {
					if (ed[x].size() - i > 2) turn = ed[x][i + 2];
				}
				else turn = ed[x][i + 1];
				break;
			}
		}
}

        在进行下一节点的遍历之前，要先对 x 的最大子节点进行检查，若最大子节点不为 r.top()，那就意味着 turn 应该被更新了。

        因为 ed[x][ed[x].size() - 1] != r.top()，所以 x 的子节点中是有一部分要在回溯时才被遍历的。那么我们就需要找出 r.top() 是 x 的第几大子节点，设这个序号为 i，排除多余边之后即可找出比 r.top() 大的子节点中编号最小的节点，turn即更新为此值。

if (x == tail) {
	brk.first = x;
	brk.second = head;
	break;
}

        在上面两步操作之前，还应该有一个边界。若遍历过了整个环都没有找到符合条件的节点，那么就断开这个环首尾相接的那条边。

}

至此！我们终于找出了要断开的边！

是时候求出答案了！

断环后在树上求解 

        这部分就容易多了，只要把60%做法的DFS稍作更改，不让它搜断开的边就好了！

void dfs(int x) {
	printf("%d ", x);
	vis[x] = 1;
	for (int i = 0; i < ed[x].size(); i++) {
		int y = ed[x][i];
		if (vis[y] || y == brk.first && x == brk.second || y == brk.second && x == brk.first) continue;
		dfs(y);
	}
	return;
}

---

 大功告成！

附上100%做法完整代码，以及供调试使用的大样例。

完整代码

#include<bits/stdc++.h>
using namespace std;
 
const int maxn = (int)5e5 + 5;
int n, m;
int head;
int tail, turn;
bool vis[maxn];
bool onrg[maxn];
pair<int, int> brk;
vector<int> ed[maxn];
stack<int> v, r, w;
queue<int> opq;
 
void dfs(int x) {
	printf("%d ", x);
	vis[x] = 1;
	for (int i = 0; i < ed[x].size(); i++) {
		int y = ed[x][i];
		if (vis[y] || y == brk.first && x == brk.second || y == brk.second && x == brk.first) continue;
		dfs(y);
	}
	return;
}
 
bool findRing(int x, int fa) {
	if (vis[x]) {
		head = x;
		onrg[x] = 1;
		tail = v.top();
		while (v.top() != x) {
			onrg[v.top()] = 1;
			r.push(v.top());
			v.pop();
		}
		return 1;
	}
 
	vis[x] = true;
	v.push(x);
	for (int i = 0; i < ed[x].size(); i++) {
		if (ed[x][i] == fa) continue;
		if (findRing(ed[x][i], x)) return 1;
	}
	v.pop();
	vis[x] = 0;
	return 0;
}
 
inline void deal() {
	if (r.top() > tail) {
		swap(r.top(), tail);
		while (!r.empty()) {
			opq.push(r.top());
			r.pop();
		}
		while (!opq.empty()) {
			r.push(opq.front());
			opq.pop();
		}
	}
	
	turn = tail;
	while (!r.empty()) {
		int x = r.top();	r.pop();
		if (x == tail) {
			brk.first = x;
			brk.second = head;
			break;
		}
		
		if (ed[x][ed[x].size() - 1] > turn && ed[x][ed[x].size() - 1] == r.top()) {
			brk.first = x;
			brk.second = r.top();
			break;
		} else {
			if (ed[x][ed[x].size() - 1] != r.top() && onrg[ed[x][ed[x].size() - 1]]) {
				if (ed[x][ed[x].size() - 2] > turn && ed[x][ed[x].size() - 2] == r.top()) {
					brk.first = x;
					brk.second = r.top();
					break;
				}
			}
		}
		
		if (ed[x][ed[x].size() - 1] != r.top()) {
			if (ed[x].size() > 2) 
				for (int i = 0; i < ed[x].size(); i++) {
					if (ed[x][i] == r.top()) {
						if (onrg[ed[x][i + 1]]) {
							if (ed[x].size() - i > 2) turn = ed[x][i + 2];
						}
						else turn = ed[x][i + 1];
						break;
					}
				}
		}
	}
	return;
}
 
int main() {
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= m; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		ed[x].push_back(y);
		ed[y].push_back(x);
	}
 
	for (int i = 1; i <= n; i++) {
		if (ed[i].size() > 1) {
			sort(ed[i].begin(), ed[i].end());
		}
	}
 
	if (n != m) dfs(1);
	else {
		findRing(1, 1);
		memset(vis, 0, sizeof(vis));
		deal();
		dfs(1);
	}
 
	return 0;
}

大样例

样例输入：

100 100
88 9
60 16
43 75
72 15
91 97
100 1
12 94
89 66
15 32
8 9
96 85
25 64
2 68
24 50
34 67
69 51
76 91
80 37
54 100
20 4
10 84
68 82
50 83
44 67
96 25
54 95
61 3
98 40
10 65
34 66
12 92
36 12
74 87
34 60
93 6
13 50
61 76
19 51
5 73
22 59
100 30
59 41
41 54
6 15
10 29
24 40
28 7
23 93
57 14
62 39
79 60
48 67
73 87
8 99
49 45
43 15
21 82
39 38
49 36
78 37
71 72
4 86
58 22
88 26
74 2
52 91
57 71
48 42
61 22
28 62
9 86
77 8
17 59
56 26
53 95
54 65
73 35
47 10
15 4
45 42
82 25
81 26
78 34
33 68
11 28
94 52
31 65
47 14
55 79
38 81
85 98
49 63
55 27
19 39
41 90
50 27
2 46
49 70
5 62
44 18

样例输出：

1 100 30 54 41 59 17 22 58 61 3 76 90 65 10 29 47 14 57 71 72 15 4 20 86 9 8 77 99 88 26 56 81 38 39 19 51 69 62 5 73 35 87 74 2 46 68 33 82 21 25 64 96 85 98 40 24 50 13 27 55 79 60 16 34 66 89 67 44 18 48 42 45 49 36 12 92 94 52 91 97 63 70 78 37 80 83 28 7 11 6 93 23 32 43 75 84 31 95 53

样例建图：

 最后，祝大家都能成为AC自动机！