[洛谷 5022,loj 2953][NOIP2018]旅行

题目链接

https://www.luogu.org/problem/P5022

https://loj.ac/problem/2953

题解

对于树的情况，我们 DFS 直接贪心先走编号小的节点即可。时间复杂度是 \(O(n)\) 的。

问题在于基环树。我们先找出环，然后枚举断掉环上的某一条边，这样就转化为了树上的问题。

时间复杂度是 \(O(n^2)\) 的，因为 \(n \leq 5000\)，所以可以轻松通过。

实现的时候，为了确保我们走编号小的节点，采用了 vector 来存边，将每个点的所有可达点排序，从编号小的点先开始遍历即可。

还有一个细节：如果当前遍历序列已经不是最优，直接回溯即可，这样可以稍微提高程序的实际运行效率。（然而加强版还是过不去）

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
int n,m;
vector<int> a[5005];
namespace tree
{
 int vis[5005],path[5005],cnt;
 void dfs(int u)
 {
  vis[u]=1;
  path[++cnt]=u;
  int s=a[u].size();
  for(int i=0;i<s;i++)
   if(!vis[a[u][i]])dfs(a[u][i]);
 }
 void solve()
 {
  for(int i=1;i<=n;i++)
   sort(a[i].begin(),a[i].end());
  dfs(1);
  for(int i=1;i<=n;i++)
   printf("%d ",path[i]);
 }
}
namespace loop
{
 int sta[5005],loop[5005],vis[5005],tmp[5005],path[5005],top,siz,fib,cnt;
 bool flag=false,is_best;
 void init(int u,int fa)
 {
  vis[u]=1;
  sta[++top]=u;
  int s=a[u].size();
  for(int i=0;i<s;i++)
   if(!vis[a[u][i]])init(a[u][i],u);
   else
   {
    if(fa!=a[u][i]&&!flag)
    {
     int num=top;
     do
     {
      loop[++siz]=sta[num--];
     }while(sta[num]!=a[u][i]);
     loop[++siz]=a[u][i];
     flag=true;
    }
   }
  sta[top--]=0;
 }
 bool is_fib(int u,int v)//判断是否走了被断掉的边
 {
  if((u==loop[fib]&&v==loop[fib+1])||(v==loop[fib]&&u==loop[fib+1]))return true;
  return false;
 }
 bool dfs(int u)
 {
  vis[u]=1,cnt++;
  if(path[cnt]>u||fib==1)is_best=true;
  if(!is_best&&path[cnt]<u)return false;//不是最优解直接回溯
  path[cnt]=u;
  int s=a[u].size();
  for(int i=0;i<s;i++)
   if(!is_fib(u,a[u][i])&&!vis[a[u][i]])
    if(!dfs(a[u][i]))return false;
  return true;
 }
 void solve()
 {
  init(1,0);//找环
  loop[++siz]=loop[1];
  for(int i=1;i<=n;i++)
   sort(a[i].begin(),a[i].end());
  for(int i=1;i<siz;i++)
  {
   memset(vis,0,sizeof(vis));
   fib=i,cnt=0,is_best=false;
   dfs(1);
  }
  for(int i=1;i<=n;i++)
   printf("%d ",path[i]);
 }
}
int main()
{
 scanf("%d%d",&n,&m);
 for(int i=1;i<=m;i++)
 {
  int u,v;
  scanf("%d%d",&u,&v);
  a[u].push_back(v);
  a[v].push_back(u);
 }
 if(m==n-1)tree::solve();
 else loop::solve();
 return 0;
}