P3443 [POI2006] LIS-The Postman 题解

· · 题解

题意

求一条以 1 为起点的欧拉回路，使得给定路口序列在路线及求出的欧拉回路序列中出现。

分析

  1. 首先，肯定是要存在欧拉路径的。而有向图中存在欧拉路径须满足以下条件：图去掉孤立点后联通和每个点的入度等于出度。
  2. 注意到规定的每个路口序列都必须在路线中连续出现，及如果我们存在路线，我们不能改变走这些规定的序列的顺序。那么相当于这些边是被限制死的了，不能改变，所以可以将它们合并为一条边。（因合并而多出来的孤立点不影响欧拉回路）

那么在我们就来考虑怎么将边合成了，如果直接按照每条序列合并的话，会发现可能存在几条序列刚好有公共部分从而卡掉我们的程序。

所以我们先给每条边编上一个编号，在维护指向这条边的上一条边和这条边指向的下一条边，及前驱和后继。

从而我们很容易发现：

  1. 一条边不能有多个后继。
  2. 几条边的指向关系不能组成一个环。
  3. 若求出一条不存在的边，那么就不行。

而维护起来也是很容易的，用 map 存边的编号，开个数组记录后继，再用循环不断合并边。

最后还有一个小技巧，及我们如果合并了边，在最后输出时还有点儿麻烦，所以=我们可以加几个数组，让程序在求欧拉回路时如果碰到了指定序列（合并后）中的边，就只能遍历完序列的边，这样输出也方便。

最终本题就解完了。

就不上代码了。

Code

#include<bits/stdc++.h>
#define int long long
#define GG printf("NIE"),exit(0)
const int M=5e5+1;
using namespace std;
vector<int>E[M];
map<int,int>g[M];
int x,y,n,m,t,k,H[M],deg[M],To[M],del[M],Ne[M],Now,Nex,S[M],Sid;
void read(int &P)
{
    int x=0;
    char c=getchar();
    while(c>'9'&&c<'0')
        c=getchar();
    while(c<='9'&&c>='0')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    P=x;
}
void dfs(int u,int from)
{
    if(from)
        dfs(To[from],Ne[from]);
    else
        for(int i=H[u];i<E[u].size();i++)
        {
            int id=E[u][i];
            H[u]++;
            if(del[id])
                continue;
            del[id]=1;
            dfs(To[id],Ne[id]);
        }
    S[++Sid]=u;
}
signed main()
{
    read(n),read(m);
    for(int i=1;i<=m;i++)
    {
        read(x),read(y);
        E[x].push_back(i);
        To[i]=y,g[x][y]=i,deg[x]++,deg[y]--;
    }
    for(int i=1;i<=n;i++)
        if(deg[i])
            GG;
    read(t);
    while(t--)
    {
        read(k),read(Now),read(Nex);
        k--,k--;
        int Last=g[Now][Nex];
        if(!Last)
            GG;
        for(int i=1;i<=k;i++)
        {
            read(x);
            int id=g[Nex][x];
            if(!id)
                GG;
            if(Ne[Last]&&Ne[Last]!=id)
                GG;
            Ne[Last]=id;
            del[id]=1;
            Now=Nex,Nex=x;Last=id;
        }
    }
    dfs(1,0);
    if(Sid!=m+1)
        GG;
    printf("TAK\n");
    while(Sid)
        printf("%lld\n",S[Sid--]);
    return 0;
}

一些更正：

确实是没考虑到限制成环的情况，还是讨论区大佬多。

所以我们对于代码加入一个小细节，使得他不重复走某条边即可。

具体地，我们开一个数组 used[i] 表示第 i 条边是否被遍历过，然后判断即可。

更正后的代码如下：

void dfs(int u,int from)
{
    if(from){
        if(used[from])
            GG;
        used[from]=1;
    }
    if(from)
        dfs(To[from],Ne[from]);
    else
        for(int i=H[u];i<E[u].size();i++)
        {
            int id=E[u][i];
            H[u]++;
            if(del[id])
                continue;
            del[id]=1;
            dfs(To[id],Ne[id]);
        }
    S[++Sid]=u;
}