NOIp 2018 day2 t1 travel

为啥这题暴力剪枝就能过啊…..一点都不科学……
太欺负人了
我来写个$\theta (NlogN)$的吧…..

基环树放day2t1不太友好吧…..算了都说了是NOIplus了对不对呀….

很明显 如果放在树上就有几个固定的性质

1 在能选择的范围之内选择最小的

2 能选择进入的是当前点u的儿子节点

3 这棵树一定以1为根

这样就可以60分了

考场上脑抽还有一点分类讨论完了结果跑去淦t2结局悲惨最后10分钟回来打了个暴力就走了

如果是基环树??

很明显只有一个环

第三个性质放在基环树上照样行得通….

有几个点需要注意一下

在环上走的话 如果你要处理儿子那么就代表直接work了他的所有后代

不向nextNode(环上的下一个点)走而是回到上一节点时需要处理这个点所有不在环上的子树..

所以你每次走是比较nextNode和不在环上的直接儿子

如果没有儿子了就把stacktop的点和nextNode比较

小的话很明显就可以弹空stack然后return到环上的初始点了 这是和暴力的根本区别

如果儿子小的话直接处理儿子

如果nextNode小的话就把儿子按照从大到小的顺序压到stack里

这时候如果nextNode已经访问过 那么就直接挨个pop然后work掉每个子树 保证了顺序的合法性

如果!top了看下在环上最开始接触的点的另外一个邻居点和环上最开始接触的点的儿子

还是按照dfs做不过不能再回头了而是一遍跑完 只比较nextNode和son 如果son空了不用管栈

这样就把环做掉了

很明显点1如果在环上的话直接做就行

如果点1不在环上

那么这个环一定是在点1的某个子树里

然后按照60分的做法就行了 如果进到环里就按照上边的做

进到环里的第一个点设成环上的初始点…

下面是分类讨论时间 注意下面的son都是直接儿子而不是所有后代

算了我还是贴上代码吧….

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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include<algorithm>
#include<cstdio>
#include<vector>

const int N = 7e5 + 7;
const int inf = 1e9 + 7;
inline int read() {
char ch = getchar();
int ret = 0, f = 1;
while (ch > '9' || ch < '0') {
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
ret = ret * 10 + ch - '0', ch = getchar();
return ret * f;
}
int last[N], cnt, root;
struct Edge {
int next, to;
} e[N * 2];
inline void add (int u, int v) {
e[++cnt].next = last[u], e[cnt].to = v, last[u] = cnt;
}

int stack[N], vis[N], cNode[N], backNode;
int top = 0;
inline int find_circle (int x, int fa) {
vis[x] = 1;
for (int i = last[x]; i; i = e[i].next) {
int to = e[i].to;
if (to == fa) continue;
if (vis[to]) {
cNode[to] = cNode[x] = 1;
backNode = to;
return 1;
}
int oncircle = find_circle (to, x);
if (oncircle && to != backNode) {
cNode[x] = 1;
return 1;
}
}

return 0;
}

int idx[N], flag = 0;
int tot = 0;
int f[N];
std :: vector<int> xNode[N];


inline void work2 (register int x, int fa) {
if (vis[x]) return ;
idx[++cnt] = x, vis[x] = 1;
for (register int i = last[x]; i; i = e[i].next) {
int to = e[i].to;
if (to == fa || vis[to]) continue;
xNode[x].push_back(to);
}
std :: sort (xNode[x].begin(), xNode[x].end());
int k = xNode[x].size() - 1;
for (register int i = 0; i <= k; i++) {
work2 (xNode[x][i], x);
}
}

inline void dfs (register int x, int fa) {
if (vis[x]) return ;
idx[++cnt] = x, vis[x] = 1;
for (register int i = last[x]; i; i = e[i].next) {
register int to = e[i].to;
if (to == fa || vis[to]) continue ;
xNode[x].push_back(to);
}
std :: sort (xNode[x].begin(), xNode[x].end());
register int k = xNode[x].size () - 1;
for (register int i = 0; i <= k; i++) {
int to = xNode[x][i];
if (vis[to]) {
for (register int j = k; j > i; j--)
stack[++top] = xNode[x][j], f[stack[top]] = x;
return;
}
if (cNode[to] && i == k) {
if (stack[top] < to && top > 0) {
return ;
}
}
if (cNode[to]) {
for (register int j = k; j > i; j--)
stack[++top] = xNode[x][j], f[stack[top]] = x;
dfs (to, x);
flag = 1;
if (x == root)
while (top && cNode[f[stack[top]]]) top--, work2 (stack[top + 1], f[stack[top + 1]]);
return ;
} else work2 (to, x);
}
}
inline void work (int x, int fa) {
if (vis[x]) return;
idx[++cnt] = x, vis[x] = 1;
for (int i = last[x]; i; i = e[i].next) {
int to = e[i].to;
if (to == fa) continue;
xNode[x].push_back(to);
}
std :: sort (xNode[x].begin(), xNode[x].end());
for (int i = 0; i < xNode[x].size(); i++) {
if (cNode[xNode[x][i]] && !flag) root = xNode[x][i], dfs (xNode[x][i], x);
else work (xNode[x][i], x);
}
}

int n, m;
int main () {
n = read(), m = read();
for (int i = 1; i <= m; i++) {
int x, y;
x = read(), y = read();add (x, y), add (y, x);
}
cnt = 0;
find_circle (1, 0);
for (int i = 1; i <= n; i++) vis[i] = 0;
if (m == n - 1) {
work (1, 0);
for (int i = 1; i <= n; i++) printf ("%d ", idx[i]);
return 0;
} else {
if (cNode[1]) root = 1, dfs (1, 0);
else work (1, 0);
}
for (int i = 1; i <= n; i++) printf ("%d ", idx[i]);
return 0;
}

所以说这题暴力和NlogN做法的本质区别就是个有序的栈和分类讨论…..

哎….心态也是实力的一部分啊….