题解 CF62D 【Wormhouse】

NXYorz · 2020-08-11 17:00:00 · 题解

题目链接

题目给你了一条欧拉回路，让你再找一条欧拉回路，使得新找到的欧拉回路的字典序在严格大于题目中给的欧拉回路的情况下，保证字典序最小。

可以考虑搜索啊....

在每一层我们都把当前节点的扩展到的节点扔到堆中，然后每一次取堆顶，从而保证了字典序是最小的。需要注意的是，字典序比较的是第一个不一样的地方，所以我们可以维护一个全局变量flag，表示我们的新的序列的字典序是否已经严格大于。

然后暴力断边，因为我建的是双向边，所以我标记的时候只考虑一对边中小的编号。如果找到符合题意的序列，直接输出即可。数据范围小啊

Code

#include<queue>

#define N 111
#define M 2101

using namespace std;

int n,m,sum;
int a[M],first[N],ans[M];
bool v[M*2],flag;

struct E
{
    int next;
    int to;
    void add(int x,int y)
    {
        next=first[x];
        to=y;
        first[x]=sum;
    }
}e[M*2];

struct NO
{
    int w;
    int num;
    bool operator < (const NO b) const
    {return w>b.w;}
};

void print()
{
    for(int i=1;i<=m+1;i++)
        printf("%d ",ans[i]);
    exit(0);
}

void dfs(int x,int loc)
{
    ans[loc]=x;
    if(loc==m+1)
    {
        if(flag) print();
        return;
    }
    priority_queue<NO> q;
    while(!q.empty()) q.pop();
    for(int i=first[x];i;i=e[i].next)
        q.push((NO){e[i].to,i});
    while(!q.empty())
    {
        NO now=q.top();q.pop();
        int i=now.num;
        if(v[i&1?i:i-1]) 
            continue;
        int to=e[i].to;
        bool bj=0;
        if(to<a[loc+1]&&!flag) 
            continue;
        if(to>a[loc+1]&&!flag) 
        {
            flag=1;
            bj=1;
        }
        v[i&1?i:i-1]=1;
        dfs(to,loc+1);
        v[i&1?i:i-1]=0;
        if(bj) flag=0;
    }
}

int main()
{
    freopen("aa.in","r",stdin);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m+1;i++)
        scanf("%d",a+i);
    for(int i=2;i<=m+1;i++)
    {
        e[++sum].add(a[i-1],a[i]);
        e[++sum].add(a[i],a[i-1]);
    }
    dfs(a[1],1);
    printf("No solution");
    return 0;
}

不知道为什么在预览中炸了，不知道会不会影响题解中的展示，但是在博客里是可以正常观看的，如果排版会炸，可以点击这里