OI - 旅行（数据加强版）(洛谷) | Lucky_Glass's Blog

以心为名，名为爱惜

0%

OI - 旅行（数据加强版）(洛谷)

发表于 分类于 Valine：

论考试前一直写WA，考试的时候碰到原题重新写代码就 A 了是什么玩意……

# 题面

> 洛谷 P5049

点击展开/折叠题面

小Y了解到，X国的 $n$ 个城市之间有 $m$ 条双向道路。每条双向道路连接两个城市。 不存在两条连接同一对城市的道路，也不存在一条连接一个城市和它本身的道路。并且， 从任意一个城市出发，通过这些道路都可以到达任意一个其他城市。小 Y 只能通过这些 道路从一个城市前往另一个城市。

小 Y 的旅行方案是这样的：任意选定一个城市作为起点，然后从起点开始，每次可 以选择一条与当前城市相连的道路，走向一个没有去过的城市，或者沿着第一次访问该 城市时经过的道路后退到上一个城市。当小 Y 回到起点时，她可以选择结束这次旅行或 继续旅行。需要注意的是，小 Y 要求在旅行方案中，每个城市都被访问到。

为了让自己的旅行更有意义，小 Y 决定在每到达一个新的城市（包括起点）时，将它的编号记录下来。她知道这样会形成一个长度为 $n$ 的序列。她希望这个序列的字典序最小。

# 解析

原题 $O(n^2)$ 可过，就直接枚举环上的边删掉，做 n 次树的简单贪心。现在要砍掉一个 $O(n)$ 的复杂度，于是不能枚举删掉哪条边。

原来的做法，删掉一条边，相当于在沿着环走到那条边的时候不继续走，而是调头“返回”。

为了方便表示，我们找到图上几个特殊的点：

png1

从点 1 第一次进入环的点是 st，沿着环走到的下一个点是 ca，一直走到 cc 然后“返回”，又从 cb 沿着环走，一直走到 cd 结束。

st 是确定的，那么 ca 一定是 st 在环上相邻的两个点中较小的，另一个是 cb。于是我们需要判断的是 cc 在哪里（cd 就是 cc 另一边的点），即在哪个点返回。

我们发现 cc,cd 具有以下性质：

  1. 记从 cc 返回到环的上一个点，按照贪心策略下一个经过的点为 mn，则 cd>mn；
  2. cd 应该比 cc 相邻的所有不在环上的点大（如果是比 cd 小的 cc 相邻的不在环上的点，则应该在 cd 之前就已经考虑，如果还存在比 cd 大的点，则返回时一定会先经过，比直接去 cd 差）

根据这两点，我们在 DFS 时，假如当前点 u 在环上，而且考虑沿着环到下一个点 v，则可以通过下面的方法判断 u 是否是 cc：

  1. v 是 u 要考虑的最后一个点（对应性质2）
  2. v 比 mn 大（对应性质1）；
  3. 当前还没有经过 cb（即不是已经返回了的情况）；

如何维护 mn？如果我们从环上的 u 沿环走到 v，则更新 mn 为 u 的下一个要考虑的点（如果存在，不存在则不更新）。可以发现当我们从 st 到 ca 时，mn 至多是 cb，一定存在。

# 源代码

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=2e6+10;

int n,m,typ;
pair<int,int> edg[N<<1],Ed[N<<1];
int nedg;

struct GRAPH{
	int head[N],to[N<<1],nxt[N<<1],ncnt;
	void AddEdge(int u,int v){
		int p=++ncnt;
		nxt[p]=head[u],to[p]=v,head[u]=p;
	}
	int operator [](const int &u){return head[u];}
}Gr;

void AddEdge(int u,int v){
	int p=++nedg,q=++nedg;
	edg[p]=make_pair(u,v);
	edg[q]=make_pair(v,u);
}
int dep[N];
int stk[N],nstk,spe,rvt;
int ton[N];
bool cir[N];
long long ans;
void DFS1(int u,int fa){
	stk[++nstk]=u;
	dep[u]=dep[fa]+1;
	for(int it=Gr[u];it;it=Gr.nxt[it]){
		int v=Gr.to[it];
		if(v==fa) continue;
		if(dep[v]){
			if(dep[v]<dep[u]){
				for(int i=nstk;stk[i]!=v;i--)
					cir[stk[i]]=true;
				cir[spe=v]=true;
				rvt=u;
			}
			continue;
		}
		DFS1(v,u);
	}
	nstk--;
}
int cnt;
void DFS2(int u,int mn){
	printf("%d ",u);
	cnt++,ans^=1ll*cnt*u;
	dep[u]=1;
	for(int it=Gr[u];it;){
		int v=Gr.to[it];
		it=Gr.nxt[it];
		if(dep[v]) continue;
		while(it && dep[Gr.to[it]]) it=Gr.nxt[it];
		if(cir[u] && cir[v] && !dep[rvt] && !it && v>mn && mn) return;
		if(cir[u]) DFS2(v,it? Gr.to[it]:mn);
		else DFS2(v,0);
	}
}
void DFS(int u){
	printf("%d ",u);
	dep[u]=1;
	for(int it=Gr[u];it;it=Gr.nxt[it]){
		int v=Gr.to[it];
		if(dep[v]) continue;
		DFS(v);
	}
}
inline int Ri(){
	register int r=0,c=getchar();
	while(c<'0' || '9'<c) c=getchar();
	while('0'<=c && c<='9') r=(r<<1)+(r<<3)+c-'0',c=getchar();
	return r;
}
int main(){
	n=Ri(),m=Ri();
	for(int i=1;i<=m;i++)
		AddEdge(Ri(),Ri());
	for(int i=1;i<=nedg;i++)
		ton[edg[i].second]++;
	for(int i=1;i<=n;i++)
		ton[i]+=ton[i-1];
	for(int i=1;i<=nedg;i++)
		Ed[ton[edg[i].second]--]=edg[i];
	for(int i=nedg;i>=0;i--)
		Gr.AddEdge(Ed[i].first,Ed[i].second);
	if(m==n){
		DFS1(1,0);
		memset(dep,0,sizeof dep);
		DFS2(1,0);
	}
	else DFS(1);
	return 0;
}

THE END

Thanks for reading!

> Linked ファンサ-bilibili