0%

NOIP2018 旅行

题目链接

晚上改题,顺便发下题解。(为什么又考原题)
其实$60$分很好拿,因为没有环,贪心就可以了。
考虑其他的$\color{red}{基环图}$的情况。

容易想到的办法是暴力删边,就是在搜索的时候如果要经过被删除的边就不合法。

#include<bits/stdc++.h>
using namespace std;

int m,n,y,x,cnt=0,step,vis[5005],k[5005],ans[5005];
vector<int> q[5005];
struct node{
    int u,v;
}edge[5005];

int read() {
    int s=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') {
        s=s*10+ch-'0';
        ch=getchar();
    }
    return s*f;
}
void add(int u,int v) {
    edge[++cnt].u=u;
    edge[cnt].v=v;
}
bool check() {
    for(int i=1;i<=n;i++)
        if(k[i]!=ans[i]) {
            if(k[i]>ans[i]) return false;
            else return true;
        }
}
void fkccf() {
    for(int i=1;i<=n;i++) ans[i]=k[i];
}
void fuckccf(int u,int fa) {
    if(vis[u]) return;
    vis[u]=1,k[++step]=u;
    if(step==n) {
        fkccf();
        return;
    }
    int top=q[u].size();
    for(int i=0;i<top;i++) {
        int nex=q[u][i];
        if(nex==fa) continue;
        fuckccf(nex,u);
    }
}
void Fuckccf(int u,int fa) {
    if(vis[u]) return;
    vis[u]=1,k[++step]=u;
    int top=q[u].size();
    for(int i=0;i<top;i++) {
        int nex=q[u][i];
        if(nex==fa|| (u==x&&nex==y) || (u==y&&nex==x)) continue;
        Fuckccf(nex,u);
    }
}

int main() {
    memset(ans,100,sizeof(ans));
    n=read();m=read();
    for(int i=1;i<=m;i++) {
        int a=read();int b=read();
        q[a].push_back(b);
        q[b].push_back(a);
        add(a,b);
    }
    if(n!=m) {
        memset(vis,0,sizeof(vis));
        for(int i=1;i<=n;i++) sort(q[i].begin(),q[i].end());
        step=0;
        fuckccf(1,-1);
        for(int i=1;i<=n;i++) printf("%d ",ans[i]);
        puts("");
        return 0;
    }
    for(int i=1;i<=n;i++) sort(q[i].begin(),q[i].end());
    for(int i=1;i<=cnt;i++) {
        x=edge[i].u,y=edge[i].v,step=0;
        memset(vis,0,sizeof(vis));
        Fuckccf(1,-1);
        if(step<n) continue;
        if(check()) fkccf();
    }
    for(int i=1;i<=n;i++) printf("%d ",ans[i]);
    puts("");
    return 0;
}