题面：

题目描述：

Bob想在公园散步。公园由n个点和m条无向边组成。当Bob到一个未经过的点时，他就会把这个点的编号记录在笔记本上。当且仅当Bob走完所有的点，他才会停下来。这时，Bob的笔记本记录了一个由n个点编号组成的序列，问：Bob能记录的字典序最小的序列。

题目分析：

这道题直观想法就是dfs：

里面还有贪心，最短路等等。

但其实呢，这个很容易被误导，我们还是要认真地分析一下题目：

先说一下错误的想法：

每一次dfs选字典序最小的点，比如这样：

但是会有这种情况：

用dfs就会一直往下遍历，输出结果就是：1 2 4 3, 但很明显，这个答案是错的，正确的答案应该是：1 2 3 4。路线：1-2-1-3-1-2-4。

有人说，那么bfs就好了啊。对于这个图来说，确实是这样（bfs遍历顺序：1-2-3-4）。但是对于下面这个图：

很明显，用bfs也是错的（用dfs会输出：1 2 4 3），正确答案：1 2 3 4，路径：1-2-3-2-1-4。

虽然我们尝试了两种方法都不行。但是，从上面的分析我们可以看到：之前走过的点是可以走回去的，只不过走过的点不记录而已。

我们可以根据这点对上面的图进行分析：

刚开始Bob从点1出发，根据字典序最小原则，Bob只能走点2才能使字典序最小：

紧接着，Bob可以在1，2间来回走动，而不改变笔记本的记录结果：

这时，我们发现只要先走：和1，2领接编号最小的点（编号为3）就可以使字典序最小：

往点3走后，Bob可以在1，2，3间来回走动，而不改变笔记本的记录结果：

这时和1，2，3这三个点相连的点只有4，那么往点4走就可以了。最后答案是：1 2 3 4，保证字典序最小。

实现：用邻接表（存图），标记数组（维护上图红色区域），优先队列（短时间找到和红色区域相连的编号最小的点）

每当从优先队列取出一个点时，肯定是与红色区域相连的编号最小的点，然后把这个点加入红色区域，再把这个点相连的点加入优先队列就可以了。

最后：其实我觉得这个有点像最小生成树prim算法的做法

AC代码：

 1 #include <cstdio>

 2 #include <cstring>

 3 #include <iostream>

 4 #include <algorithm>

 5 #include <vector>

 6 #include <queue>

 7 using namespace std;

 8 const int maxn = 1e5+5;

 9 int n, m;

10 vector<int> G[maxn];  //vector版邻接表

11 int vis[maxn];  //标记数组

12

13 struct cmp{   //比较函数，优先小的在队列前面

14     bool operator () (int a, int b){

15         return a > b;

16     }

17 };

18

19 void solve(){

20     priority_queue<int, vector<int>, cmp> q;

21     int u;

22     q.push(1);

23

24     while(!q.empty()){

25         u = q.top(); q.pop();

26

27         if(vis[u]) continue;  //防止重复访问

28         vis[u] = 1;    //标记

29

30         printf("%d ", u);   //输出答案

31

32         for(int i = 0; i < G[u].size(); i++){

33             q.push(G[u][i]);

34             //把和u相连的点加入优先队列

35         }

36     }

37 }

38

39 int main(){

40     scanf("%d%d", &n, &m);

41

42     int u, v;

43     for(int i = 1; i <= m; i++){

44         scanf("%d%d", &u, &v);

45         G[u].push_back(v);

46         G[v].push_back(u);

47     }

48

49     solve();

50

51     return 0;

52 }

巴特西

Codeforces Round #538 D. Lunar New Year and a Wander

题面：

题目描述：

题目分析：

最新文章

热门文章