题解 P6983 【[NEERC2015]King’s Inspection】

Su_Zipei · 2020-11-04 11:34:20 · 题解

首先发现这题要求的是哈密顿回路，然后一看是NPC问题瞬间劝退。。其实是有特点的，对于这道题来说，特点就是合法的图中出度大于2的点不会很多，最多只有20个，而对于出度为1的点是没必要去跑的，因为知道走上去之后的结果，所以事实上只需要对这二十个点跑一下就行，那么可以把所有的链都缩起来，这样时间复杂度的极限也才20*2^{20}，可以通过。

#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2e5+10;
struct Edge{
    int to,nxt;
}e[N<<1];
int n,m;
int h[N],idx,nxt[N],d[N];
void Ins(int a,int b){
    e[++idx].to=b;e[idx].nxt=h[a];h[a]=idx;
}
vector<int> vec;
bool vis[N],inq[N];
bool check(){
    memset(inq,0,sizeof(inq));
    for(int i=1,now=1;i<=n;i++,now=nxt[now]){
        if(inq[now])return 0;
        inq[now]=1;
    }
    return 1;
}
void dfs(int u){
    if(u==vec.size()){
        if(check()){
            for(int i=1,now=1;i<=n;i++,now=nxt[now])
                printf("%d ",now);
            printf("1 ");
            exit(0);
        }
        return;
    }
    int now=vec[u];
    for(int i=h[now];i;i=e[i].nxt){
        int v=e[i].to;
        if(vis[v])continue;
        vis[v]=1;
        nxt[now]=v;
        dfs(u+1);
        vis[v]=0;
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        Ins(a,b);d[a]++;
    }
    for(int i=1;i<=n;i++){
        if(d[i]>=2)vec.push_back(i);
        else if(d[i]==0)return puts("There is no route, Karl!"),0;
        else {
            int v=e[h[i]].to;
            if(vis[v])return puts("There is no route, Karl!"),0;
            vis[v]=1;
            nxt[i]=v;
        }
    }
    dfs(0);
    return puts("There is no route, Karl!"),0;
}