题解 P5022 【旅行】

写一篇简单的题解造福社会。 对于树上的情况，能参加提高组的oier都应该可以想出来只要给一个点所能到达的点的编号进行一次从小到大的排序的贪心思想，在树上dfs一遍即可解决。 但是对于基环树上的情况呢？这个就有区分度了。~~考场上的我看到基环树想都没想就跑t2了~~ 似乎有很多人会以为用一个priority_queue维护可以到达（包括绕回去）的点即可，实际上可以构造出很多反例，例如这一棵基环树  你如果想要用优先队列维护，答案是`123456`，然而正确答案显然为`123645`。那么如何解决呢？ 我们可以考虑删边进行这个操作。基环树有一个很好的性质，删了一条边就变成一棵树。如果我们手玩一下基环树的样例可以发现：必定有一条边是不会经过的，因此就可以想到删边，然后类似于在树上进行贪心的思路即可。 代码也就很简单了。我个人认为代码可读性很高。 ``` #include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <cstring> #include <cctype> #include <vector> using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();} while (isdigit(ch)){x=x*10+ch-48;ch=getchar();} return x*f; } int n,m; vector <int> G[5050]; int ans[5050],edge[5050][2]; namespace solve1 { int cnt=0; bool vis[5050]; inline void dfs(int u,int fa) { ans[++cnt]=u; vis[u]=true; for (int i=0;i<G[u].size();i++) { int v=G[u][i]; if (!vis[v]) dfs(v,u); } } void main() { memset(ans,0,sizeof(ans)); memset(vis,0,sizeof(vis)); cnt=0; for (int i=1;i<=n;i++) sort(G[i].begin(),G[i].end()); dfs(1,0); for (int i=1;i<=n;i++) printf("%d ",ans[i]); } } namespace solve2 { int cnt=0,res[5050]; bool vis[5050]; inline bool comp() { for (int i=1;i<=n;i++) if (ans[i]!=res[i]) return ans[i]>res[i]; return false; } int del_u,del_v; inline bool check(int u,int v) { if ((u==del_u && v==del_v) || (u==del_v && v==del_u)) return false; return true; } inline void dfs(int u,int fa) { res[++cnt]=u; vis[u]=true; for (int i=0;i<G[u].size();i++) { int v=G[u][i]; //cout << u << " " << v << " " << del_u << " " << del_v << endl; if (!vis[v] && check(u,v)) dfs(v,u); } } void main() { memset(ans,0x3f,sizeof(ans)); memset(vis,0,sizeof(vis)); for (int i=1;i<=n;i++) sort(G[i].begin(),G[i].end()); for (int i=1;i<=m;i++) { cnt=0; memset(res,0,sizeof(res)); memset(vis,0,sizeof(vis)); del_u=edge[i][0]; del_v=edge[i][1]; dfs(1,0); /* for (int i=1;i<=n;i++) cout << res[i] << " "; cout << cnt << endl; */ if (comp() && cnt==n) memcpy(ans,res,sizeof(res)); } for (int i=1;i<=n;i++) printf("%d ",ans[i]); } } int main() { n=read(),m=read(); for (int i=1;i<=m;i++) { int u=read(),v=read(); G[u].push_back(v); G[v].push_back(u); edge[i][0]=u; edge[i][1]=v; } if (m==n-1) solve1::main(); else solve2::main(); return 0; } ``` 然后这份代码在不开O2的情况下是会tle的。（少爷机可能不会，手头上没有8700k）原因如下： 1、vector实在是太慢了，建议手写一个或者用链式前向星进行存图。 2、有很多无用的情况。无用的情况就是当删的这条边不在环上的时候，这样删去这条边，这个图就不连通了，可以直接剪枝。 如果在这上面进行好优化，码长++，时间--。 --- 不过还有一种很神仙的O(n)做法，好像是一边删一边维护什么的？不太会。 以及听说这个题目可以扩展到仙人掌上，甚至可以维护动态图连通性而扩展到dag上？