【NOIP2018】【洛谷P5022】旅行【基环树】

本文主要是介绍【NOIP2018】【洛谷P5022】旅行【基环树】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意：

题目链接：https://www.luogu.org/problemnew/show/P5022
给出一棵$n$个点$n$或$n-1$条边的图，从任意点开始遍历的方法的字典序。

---

思路：

很明显，开始肯定是要在点$1$，这样才能保证字典序最小。
建图时要先排序，保证邻接表访问的顺序到达点是升序。也是为了保证字典序最小。
然后分类讨论。

---

1.树（$n$点$n-1$边）

从点$1$开始暴力跑，因为每次会跑到编号最小的节点，所以跑一边的答案就是最终答案。

---

2.基环树（$n$点$n$边）

找到环，断环，然后按树跑就可以了。

---

但是这道题还是很恶心，打了我$2h$。
一开始用邻接矩阵还$T$了。。。

---

代码：

//代码丑见谅
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;const int N=5010;
int n,m,s,ans[N],a[N],tot,head[N];
bool vis[N],v[N],ok;struct edge
{int next,to;
}e[N*2];struct node
{int x,y;
}map[N*2];  //排序用void add(int from,int to)
{e[++tot].to=to;e[tot].next=head[from];head[from]=tot;
}void ask(int x,int fa,int xx,int yy)
{if (x==1) s=0;a[++s]=x;vis[x]=1;for (int i=head[x];~i;i=e[i].next){int y=e[i].to;if (!vis[y])if ((x!=xx||y!=yy)&&(x!=yy||y!=xx))  //断环ask(y,x,xx,yy);}vis[x]=0;
}void check() //求最优答案
{for (int i=1;i<=n;i++)if (a[i]<ans[i]) break;else if (a[i]>ans[i]) return;memcpy(ans,a,sizeof(a));
}void dfs(int x,int fa)
{if (v[x])  //找到环{ok=1;return;}v[x]=1;for (int i=head[x];~i;i=e[i].next)if (e[i].to!=fa) {int y=e[i].to;dfs(y,x);if (ok)  //已经有环了{ask(1,0,x,y);check();return;}}v[x]=0;
}bool cmp(node x,node y)
{if (x.x<y.x) return 1;if (x.x>y.x) return 0;if (x.y<y.y) return 0;return 1;
}int main()
{memset(head,-1,sizeof(head));scanf("%d%d",&n,&m);for (int i=1;i<=m;i++){scanf("%d%d",&map[i].x,&map[i].y);map[i+m].x=map[i].y;map[i+m].y=map[i].x;}sort(map+1,map+1+m*2,cmp);for (int i=1;i<=2*m;i++)add(map[i].x,map[i].y);if (n>m){ask(1,0,-1,-1);for (int i=1;i<=n;i++)printf("%d ",a[i]);}else{memset(ans,0x3f3f3f3f,sizeof(ans));dfs(1,0);for (int i=1;i<=n;i++)printf("%d ",ans[i]);}return 0;
}

这篇关于【NOIP2018】【洛谷P5022】旅行【基环树】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---