题解 P5049 【[NOIP2018 提高组] 旅行 加强版】

SpeMars · 2021-01-26 22:02:35 · 题解

旅行加强版可以用vector插排900ms卡过

当m=n-1时

首先讲一下m=n-1的思路,

此时这个图就是一棵树

所以图(树)上路径是唯一的

先建一颗以1为根的树

预处理每个节点的子节点的顺序，可以用数组排序，但是毕竟是加强版的数据，

所以可以用优先队列处理

优先队列只维护最小值，这与求最小字典序的基本思路臭味相投不谋而合

那么60pts就可以这么打:

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
const int N=5e5+1;
int n,m,u,v;
vector<int> g[N];
priority_queue<int> q[N];
inline int read(){
    int s=0;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar());
    for(;isdigit(ch);ch=getchar())s=(s<<1)+(s<<3)+(ch^48);
    return s;
}
void minson(int u,int fa){//处理每个节点子节点的当前最小子节点
    for(register int i=0;i<g[u].size();++i){
        int v=g[u][i];
        if(v==fa)continue;
        q[u].push(-v),minson(v,u);
            //本人很懒，直接存相反数达到小根堆的效果
    }
    return;
}
void dfs(int u){
    printf("%d ",u);
    for(;q[u].size();){//从1开始每个节点都选取最小的子节点,没有就返回
        int v=-q[u].top();
        q[u].pop();
        dfs(v);
    }
    return;
}
int main(){
    n=read(),m=read();
    for(register int i=1;i<=m;++i){
        u=read(),v=read();
        g[u].push_back(v);
        g[v].push_back(u);
    }
    minson(1,-1);
    dfs(1);
    return 0;
}

愉快の骗了60分

本题重心就在此，前面都是废话:

当m=n的情况

这样原来的图不再是一棵树，也就是说路径不唯一，这时我们要考虑其他方法

通过手玩数据可以得知这m条边里只用走m-1条边,也就是说这也是一棵树

但是要删去一条边，接下来考虑如何删边

由于m=n所以图中必然存在环,且只有一个(请自行体会)

那么我们的首要任务是找出这个环并找到入环点

据说许多神犇和奆佬都会用tarjon判环,身为蒟蒻的我打了个不知道什么の判环

判环函数:

//使用时先将根节点1传入并将vis[1]设为true
void circle(int u,int fa){
    for(register int i=0;i<g[u].size();++i){
        int v=g[u][i];
        if(v==fa)continue;
        if(vis[v]){//如果这个节点去过了则说明整个环已经被走了一遍了
                //v则为入环点,存进huan数组
            huan[++p]=v;
            huan[++p]=u;
            inhuan[u]=inhuan[v]=true;
            return;
        }
        vis[v]=true;
        circle(v,u);
        if(ok)return;//环存完了直接返回
        if(p){//如果存在环
            if(u==huan[1]){//如果又回到了入环点
                phuan=fa;//记录入环点的父节点
                ok=true;
                return;
            }
                    //在环里存入这个节点，并直接返回
            huan[++p]=u;
            inhuan[u]=true;
            return;
        }
    }
    return;
}

然后我们分析一下这个环的特点:

先安利一波非常好用の图论编辑器:

图论编辑器传送门

环里有8,9,7,10,12,11,4这些点

接下来我们就要对环里的每一个节点的子节点排序

这些子节点不能是入环点的父节点也不能是环里的节点

排序好后怎么断边呢?

首先我们从3这个点进入8后就入环了，我们看看左右哪个点小就往哪里走

如图所示往4走

往4走后就要考虑下一点走哪里，我们发现4的子节点里2最小

所以我们就会先遍历4の子树

因为遍历完后就要考虑下一次去哪个点，11明显大于9所以我们要掉头回到9

这么一来4-11这条边就没有任何利用价值了,去掉这条边后就又回到了一棵树的情况了

这样就十分简单了，将4-11这条边断掉后就可以愉快求解了!

再来看这种情况：(也是本人认为最有代表性の栗子)

环里有8,11,7,10,14,9这些点

接下来我们就要对环里的每一个节点的子节点排序

这些子节点不能是入环点的父节点也不能是环里的节点

我们会发现9这个节点小于11所以我们遍历完8的子树中小于9的部分后就可以往9走了

∵8子树剩余部分在断边回溯后一定会被访问,把8的子树里的第一个>9的节点记作cut

把环上下一个点记作nxt

然后再康康9的子树里是否有比nxt小的数，可以先将他们遍历,在康康有没有剩余节点

若有,cut的值要更新为当前节点第一个大于nxt的节点,也就是说再次回溯只能回到此处

若没有,就比较cut与nxt的值

若nxt>cut，那么我们就要回溯，去往cut,断掉nxt与当前节点的连边

若cut>nxt，就重复前面的操作，先走向nxt

对于这个栗子来说，我们遍历完9及其子树后，我们不需要前往14，

我们要回到13这个节点，所以就可以断掉9-14这条边了。

接下来就是又臭又长简洁明了の代码了:

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
const int N=5e5+1;
bool vis[N],inhuan[N],ok;
int n,m,u,v,cnt,phuan,huan[N],p,du,dv,inf=0x7fffffff;
vector<int> g[N],maxson[N];
priority_queue<int> q[N];
inline int read(){
    int s=0;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar());
    for(;isdigit(ch);ch=getchar())s=(s<<1)+(s<<3)+(ch^48);
    return s;
}
void circle(int u,int fa){
    for(register int i=0;i<g[u].size();++i){
        int v=g[u][i];
        if(v==fa)continue;
        if(vis[v]){
            huan[++p]=v;
            huan[++p]=u;
            inhuan[u]=inhuan[v]=true;
            return;
        }
        vis[v]=true;
        circle(v,u);
        if(ok)return;
        if(p){
            if(u==huan[1]){
                phuan=fa;
                ok=true;
                return;
            }
            huan[++p]=u;
            inhuan[u]=true;
            return;
        }
    }
    return;
}
void maxhuanson(){
    for(register int i=1;i<=p;++i){
        int u=huan[i];
        maxson[u].push_back(inf);//先在每个环里节点的子树里添加极值
        for(register int j=0;j<g[u].size();++j){
            int v=g[u][j];
            if(v!=phuan&&!inhuan[v])maxson[u].insert(upper_bound(maxson[u].begin(),maxson[u].end(),v),v);
                    //二分插排(注意入环节点父亲和环中节点不计入其中)
        }
    }
    return;
}
void delpath(){
    int dir,cut;
    if(huan[2]<huan[p])dir=1;//判方向
    else dir=-1;
    if(dir==1){
        du=huan[p],dv=huan[1];//如果判断边顺利进行，就直接断最后两边
        cut=huan[p];//默认cut为环的另一头(eg_1就是这样的)
        for(register int i=1;i<p;++i){
            int u=huan[i];
            int nxt=i+1;
            nxt=huan[nxt];
            if(maxson[u][0]){
                int cut_p;
                cut_p=maxson[u][upper_bound(maxson[u].begin(),maxson[u].end(),nxt)-maxson[u].begin()];
                if(cut_p!=inf)cut=cut_p;//如果存在非极值的比nxt大的第一个子节点，更新cut
            }
            if(nxt>cut){//如果回溯更优,就断nxt与当前节点的连边
                du=nxt;
                dv=u;
                return;
            }
        }
    }
    if(dir==-1){//同理
        du=huan[2],dv=huan[1];
        cut=huan[2];
        for(register int i=p;i>2;--i){
            int u=huan[i];
            int nxt=i-1;
            nxt=huan[nxt];
            if(maxson[u][0]){
                int cut_p;
                cut_p=maxson[u][upper_bound(maxson[u].begin(),maxson[u].end(),nxt)-maxson[u].begin()];
                if(cut_p!=inf)cut=cut_p;
            }
            if(nxt>cut){
                du=nxt;
                dv=u;
                return;
            }
        }
    }
    return;
}
void minson(int u,int fa){
    for(register int i=0;i<g[u].size();++i){
        int v=g[u][i];
        if((du==u&&dv==v)||(du==v&&dv==u))continue;//除去断边
        if(v==fa)continue;
        q[u].push(-v),minson(v,u);
    }
    return;
}
void dfs(int u){
    printf("%d ",u);
    for(;q[u].size();){
        int v=-q[u].top();
        q[u].pop();
        dfs(v);
    }
    return;
}
int main(){
    n=read(),m=read();
    for(register int i=1;i<=m;++i){
        u=read(),v=read();
        g[u].push_back(v);
        g[v].push_back(u);
    }
    vis[1]=true;
    circle(1,-1);
    maxhuanson();
    delpath();
    minson(1,-1);
    dfs(1);
    return 0;
}

最后就欢乐AC了,hhhhhhhh

(这码量也就算半个业界大毒瘤了)