[NOIP提高组2018day2t1]旅行

题目描述

给定n个城市，m条双向道路的图，不存在两条连接同一对城市的道路，也不存在一条连接一个城市和它本身的道路。并且，从任意一个城市出发，通过这些道路都可以到达任意一个其他城市。小 Y 只能通过这些道路从一个城市前往另一个城市。
小 Y 的旅行方案是这样的：任意选定一个城市作为起点，然后从起点开始，每次可以选择一条与当前城市相连的道路，走向一个没有去过的城市，或者沿着第一次访问该城市时经过的道路后退到上一个城市。当小 Y 回到起点时，她可以选择结束这次旅行或继续旅行。需要注意的是，小 Y 要求在旅行方案中，每个城市都被访问到。(注意：同一条道路不能走两遍，也就是回头路只能走一次)
为了让自己的旅行更有意义，小 Y 决定在每到达一个新的城市（包括起点）时，将它的编号记录下来。她知道这样会形成一个长度为 nn 的序列。她希望这个序列的字典序最小，你能帮帮她吗？对于两个长度均为 n 的序列 A和 B，当且仅当存在一个正整数 x，满足以下条件时，我们说序列 A 的字典序小于 B。

对于任意正整数 1≤i<x，序列A的第 i 个元素 Ai 和序列 B 的第 i 个元素 Bi 相同。
序列 A 的第 x 个元素的值小于序列 B 的第 x 个元素的值。

题目大意

给你一个图，让你找到字典序最小的访问顺序。

解法

因为图近似一棵树，对于前15组数据，是一棵树，我们就只需要每次按照当前节点子节点从小到大的顺序来排列就可以了。（这个东西应该是贪心）
那么对于接下来的几组数据，因为多了一条边，那么就一定会形成环，我们就每一次拆掉一条边，做和前面的做法一样的就可以了。

AC代码

#include<bits/stdc++.h>
#define ms(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define N 5005
#pragma GCC optimize(2)
using namespace std;
struct edge{
    int u,to;
}E[N<<1];
vector<int>G[N];
int ans[N],H[N];
int n,m,tot,cnt,sign1,sign2;
bool vis[N];
int read(){
    int w=0,x=0;char ch=0;
    while(!isdigit(ch))w|=ch=='-',ch=getchar();
    while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return w?-x:x;
}
void dfs(int u,int fa){
    if(vis[u])return;
    vis[u]=1;
    ans[++tot]=u;
    for(int i=0;i<(int)G[u].size();i++){
        int v=G[u][i];
        if(v==fa||(v==sign1&&u==sign2)||(v==sign2&&u==sign1)) continue;
        dfs(v,u);
    }
}
bool judge(int *a,int *b){
    for(int i=1;i<=n;i++) {
        if(a[i]==b[i]) continue;
        else return a[i]<b[i];
    }
    return true;
}
int main(){
    n=read(),m=read();
    for(int i=1;i<=m;i++){
        int u=read(),v=read();
        G[u].pb(v);
        G[v].pb(u);
        E[++cnt]=(edge){u,v};
        E[++cnt]=(edge){v,u};
    }
    for(int i=1;i<=n;i++) sort(G[i].begin(),G[i].end());
    if(m==n-1){
        ms(vis,0);
        tot=0;
        dfs(1,-1);
        for(int i=1;i<=n;i++) printf("%d ",ans[i]);
    }
    else{
        for(int i=1;i<=cnt;i+=2){
            sign1=E[i].u,sign2=E[i].to;
            ms(vis,0); tot=0; int res[N]; for(int j=1;j<=n;j++) res[j]=ans[j];
            dfs(1,-1);
            if(tot==n){
                if(res[1]==0) continue;
                if(judge(res,ans)) for(int j=1;j<=n;j++) ans[j]=res[j];
            }
            else for(int j=1;j<=n;j++) ans[j]=res[j];
        }
        for(int i=1;i<=n;i++) printf("%d ",ans[i]);
    }
    return 0;
}

nlogn的做法

\(update / by / 2019/3/1\)
虽然能\(n^2\)过百万，但是我们还是有必要研究一下基环树这个玩意的。
基环树就是在一棵树上加了一条边从而变成了带环的树。
自己在做题的时候一个不小心乱搞\(yy\)了一种基环树的做法（可能就是原来的做法，但是我在做的时候没有看过题解，纯属瞎蒙）：我们从1开始递归，那么我们一边标记一边递归，如果递归到了第一个有标记的节点，那么这个节点一定是我们环上的入点，也就是第一次进入环的节点，证明略。那么我们就在这个过程中记录父亲，最后在将入点的父亲变成我们遍历的倒数第二个节点就可以了。这样子我们就将所有的环内的节点的父亲穿在了一起，也就是说我们可以通过用父亲来遍历整个环。
以上就是我自己yy出的查环做法。
先给出查询的代码：

void find_in_point(int u,int ft){
    if (vis[u]){if(fg){fg=0;st=u;fa[u]=ft;return;}else return;}
    fa[u]=ft; vis[u]=1;
    for (int i=0;i<(int)G[u].size();i++){
        int v=G[u][i];
        if (v==ft) continue;
        find_in_point(v,u);
    }
}
void get_loop(int u,int g){
    loop[++sum]=u;
    flg[u]=1;
    if (fa[u]==g) return;
    get_loop(fa[u],g);
}

接下来就是O(n)或者是O(nlogn)查环，我做了两种方法，不过有一种方法有bug在你谷测评只有96分，巨难受qwq，如果有知道为什么会错的小伙伴请在下方留言或者私信，谢谢，下方给出96分代码。（不要吐槽沃，我太菜了）

# include<bits/stdc++.h>
# define ms(a,b) memset(a,b,sizeof(a))
# define pb push_back
# define inf 0x7f7f7f7f
# define LL long long
# define N 500005
using namespace std;
vector<int>G[N];
int fa[N],ans[N],loop[N],nxt[N],mxs[N],clo[N];
bool vis[N],fg,flg[N];
int st,n,m,s1,s2,tot,sum,num;
inline int gi(){
    int w=0,x=0;char ch=0;
    while(!isdigit(ch))w|=ch=='-',ch=getchar();
    while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return w?-x:x;
}
void dfs(int u,int fa){
    ans[++tot]=u;
    for (int i=0;i<(int)G[u].size();i++){
        int v=G[u][i];
        if (v==fa||(s1==u&&s2==v)||(s1==v&&s2==u)) continue;
        dfs(v,u);
    }
}
void find_in_point(int u,int ft){
    if (vis[u]){if(fg){fg=0;st=u;fa[u]=ft;return;}else return;}
    fa[u]=ft; vis[u]=1;
    for (int i=0;i<(int)G[u].size();i++){
        int v=G[u][i];
        if (v==ft) continue;
        find_in_point(v,u);
    }
}
void get_loop(int u,int g){loop[++sum]=u;flg[u]=1;if (fa[u]==g) return;get_loop(fa[u],g);}
int find(int u,int sta){
    int res=inf;
    for (int i=0;i<(int)G[u].size();i++){
        int v=G[u][i];
        if (v>sta&&!flg[v]) res=min(res,v);
    }
    return (res==inf)?0:res;
}
void init(int u,int ft,int cl){
    clo[u]=cl;
    if (u==st){
        int nt=inf,cnt=0;
        for (int i=0;i<(int)G[u].size();i++){int v=G[u][i]; if (flg[v]) nt=min(nt,v),num=max(num,v); else mxs[u]=max(mxs[u],v);}
        mxs[u]=cnt; nxt[u]=nt; if (cnt>=2) init(nt,u,-1); else init(nt,u,-1); return;
    }
    for (int i=0;i<(int)G[u].size();i++){
        int v=G[u][i];
        if (v==st||v==ft) continue;
        if (!flg[v]) mxs[u]=max(mxs[u],v);
    }
    for (int i=0;i<(int)G[u].size();i++){
        int v=G[u][i];
        if (!flg[v]||v==ft) continue;
        nxt[u]=v;
        if (v==st) continue;
        if (mxs[u]!=-1) init(v,u,u); else init(v,u,cl);
    }
}
void cut(int u,int fa){
    if (u==st){cut(nxt[u],u);return;}
    int v=nxt[u],tmp=-inf;
    if (v==st||v==0){s1=u;s2=st;return;}
    if (clo[u]!=-1) tmp=find(clo[u],u);
    if (v<mxs[u]||v<tmp||v<u||(num>v&&clo[u]==-1&&mxs[u]!=0)) cut(v,u);
    else{s1=u;s2=v;return;}
}
int main(){
    n=gi(),m=gi();
    for (int i=1;i<=m;i++){
        int u=gi(),v=gi();
        G[u].pb(v); G[v].pb(u);
    }
    for (int i=1;i<=n;i++) sort(G[i].begin(),G[i].end());
    s1=s2=-1;
    if (!(n^m)){
        ms(vis,0); ms(flg,0); fg=1; find_in_point(1,0);
        sum=0; get_loop(st,st);
        ms(mxs,-1); ms(clo,-1); mxs[st]=0; init(st,0,-1);
        cut(st,0);
    }
    dfs(1,0);
    if (ans[10]!=0) for (int i=1;i<=n;i++) printf("%d ",ans[i]); else for (int i=1;i<=n;i++) printf("0 ");
    return 0;
}

一些自己做的数据（对拍调试时自己错误的一些部分）

10 10
1 2
2 7
7 5
5 6
6 4
4 8
8 1
8 10
3 4
3 9

ans=1 2 7 5 6 4 3 9 8 10 

10 10
1 3
2 4
3 5
4 3
5 9
6 1
7 2
8 5
9 1
10 1

ans=1 3 4 2 7 5 8 6 9 10 

10 10
1 5
2 5
3 2
4 2
5 9
6 7
7 5
8 2
9 3
10 2

ans=1 5 2 3 4 8 10 7 6 9 

10 10
5 10
4 1
6 2
1 7
9 2
3 8
7 6
9 4
2 10
2 3

ans=1 4 7 6 2 3 8 9 10 5

nlogn做法ac代码

做法：因为我们的回溯是有条件的，那么我们必须要判断如果回溯能否最优，那么我们就考虑当前的回溯能否是答案更优，因为这是字典序最小，所以我们的答案只有一个，肯定满足某个特殊的单调性，那么我们就递归搜索当前节点的子节点中最小的能否满足当前的决策的答案，将这个标记一直传递下去。

# include<bits/stdc++.h>
# define ms(a,b) memset(a,b,sizeof(a))
# define pb push_back
# define inf 0x7f7f7f7f
# define LL long long
# define N 500005
using namespace std;
vector<int>G[N];
int fa[N],ans[N],to[N<<2],S[N],s[N],de[N];
bool flg[N],vis[N];
int n,m,cir,cnt,sum,top,len;
inline int gi(){
    int w=0,x=0;char ch=0;
    while(!isdigit(ch))w|=ch=='-',ch=getchar();
    while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return w?-x:x;
}
void solve(){
    memset(flg,1,sizeof(flg));
    for (int i=1;i<=n;i++) flg[i]=true;
    top=0;
    for (int i=1;i<=n;i++){
        if (de[i]==1) S[++top]=i;
    }
    while(top){
        int u=S[top--];
        flg[u]=0,cnt--;
        for (int j=0;j<(int)G[u].size();j++){
            int v=G[u][j];
            de[v]--;
            if (de[v]==1) S[++top]=v;
        }
    }
}
void dfs(int u,int last,int fa){
    if(!vis[u]){
        ans[++sum]=u;
        if (flg[u]) cnt--;
    }
    vis[u]=1;
    int l=len+1,r=len;
    for (int i=0;i<(int)G[u].size();i++){
        int v=G[u][i];
        if (!vis[v]) to[++len]=v;
    }
    if (len<l) return;
    r=len,len++;
    sort(to+l,to+1+r);
    if (s[u]==0) s[u]=1;
    for (s[u]=l;s[u]<=r;++s[u]){
        if (s[u]==r){
            if (flg[to[s[u]]]&&flg[u]&&flg[fa]&&to[s[u]]>last&&cir<0){
                cir=1;
                return;
            }
            dfs(to[s[u]],last,u);
        }
        else dfs(to[s[u]],to[s[u]+1],u);
    }
}
int main(){
    n=gi(),m=gi();
    for (int i=1;i<=m;i++){
        int u=gi(),v=gi();
        G[u].pb(v); G[v].pb(u);
        de[u]++; de[v]++;
    }
    for (int i=1;i<=n;i++) sort(G[i].begin(),G[i].end());
    if (!(n^m)) { cir=-1; cnt=n; solve(); flg[0]=true;}
    dfs(1,n+1,0);
    for (int i=1;i<=n;i++) printf("%d ",ans[i]);
    return 0;
}

秒客网