题解 P5022 【旅行】

一个昵称 · 2019-11-09 17:17:42 · 题解

一个DFS

这道题要求求出字典序最短的路径 如果一种情况一种情况地搜 肯定会T 所以我们这里用到一个贪心的思路 即 一个点 若连着若干个点 那么 先搜数字小的点 这样 只需要搜一遍 就可以保证得到的答案是字典序最小的

然后 这题需要分两种情况考虑 一种是 边数为n-1的情况 一种是边数为n 的情况（因为当边数为n时 会成环 当成环时 就可能会出现正解无法被搜索到的情况 如 有一个1-2-3-4连起来的环 DFS搜索的结果是1 2 4 3（因为DFS的特点就是要搜到底才会回溯）但是 答案是1 2 3 4 ） 但是 对于边数为n 的情况 我们可以把它转换为边数为n-1的情况 即 将n条边中的某一条删去 则此时总边数就会变为n-1 就可以快乐的DFS了 稍微需要注意的一点是 要判断一下删去这条边 会不会出现某个点没有边与他连接 不然就会T

下面是代码

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int n,m,ind=0;

vector <int> G[5001];

int a[5001][3];

int vis[5001];

int tp[5001];

int ans[5001];

void dfs(int s,int p,int q){
    if(vis[s]) return ;
    if(ind>n) return;
    vis[s]=1;
    tp[++ind]=s;
    if(ind==n){
        if(ans[1]==0){
            for(int i=1;i<=n;i++){
                ans[i]=tp[i];
            }
        }
        else{
            for(int i=1;i<=n;i++){
                if(ans[i]<tp[i]){
                    break;
                }
                else if(ans[i]>tp[i]){
                    for(int j=1;j<=n;j++){
                        ans[j]=tp[j];
                    }
                    break;
                }
            }
        }
    }
    for(int i=0;i<G[s].size();i++){
        if(s==p&&G[s][i]==q) continue;
        if(s==q&&G[s][i]==p) continue;//判断删边
        dfs(G[s][i],p,q);
    }
    vis[s]=0;//回溯清标记
}

int main(){
    cin>>n>>m;
    for(int i=1,u,v;i<=m;i++){
        cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);  
        a[i][1]=u;
        a[i][2]=v;
    }
    for(int i=1;i<=n;i++){
        sort(G[i].begin(),G[i].end());
    }
    for(int i=0,p,q;i<=m;i++){
        p=a[i][1];
        q=a[i][2];
        if(G[p].size()==1||G[q].size()==1) continue;//判断是否还会成一棵树
        ind=0;
        dfs(1,p,q);
        if(m==n-1) break;
    }
    for(int i=1;i<=n;i++){
        cout<<ans[i]<<" ";
    }
    return 0;
}