题解 P6378 【[PA2010]Riddle】

· · 题解

首先不难看出对于本题的点与点之间的限制关系，我们可以考虑用2-SAT来解决，通过从状态x向状态y连一条有向边表示若状态x存在，那么状态y必须存在。

接下来的处理中，x表示点x被选为关键点，x^\prime表示点x没有选为关键点，x \longrightarrow y表示两个状态之间连一条有向边。

对于每条边至少有一个端点是关键点这一限制，若边两端为x和y，那么直接进行x^\prime \longrightarrow y\ ,\ y^\prime \longrightarrow x即可。

处理使得每个部分恰有一个关键点这一限制时，发现要进行像一个点向该部分中除它以外的所有点连边的操作，这样的话，边数会达到n^2级别，这是不可以接受的，所以要考虑优化建图。

对于每个点，我们这里在其所在的部分中考虑，每个点用a_i来表示，再对其新增一个状态pre_i，表示在该部分中前i个点是否有点被选为关键点。

连边时我们可以进行以下的操作：

a_i \longrightarrow pre_{a_i}\ ,\ pre_{a_i}^\prime \longrightarrow a_i^\prime pre_{a_{i-1}} \longrightarrow pre_{a_i}\ ,\ pre_{a_i}^\prime \longrightarrow pre_{a_{i-1}}^\prime\ \ pre_{a_{i-1}} \longrightarrow a_i^\prime\ ,\ a_i \longrightarrow pre_{a_{i-1}}^\prime

通过这样的前缀优化建图，就不用再连那么多边了，同时题目的限制条件也都可以满足。

具体实现细节看代码吧。

code: 
#include<bits/stdc++.h>
#define p1(x) x
#define p0(x) x+n
#define pre1(x) x+2*n
#define pre0(x) x+3*n
#define maxn 8000010
using namespace std;
template<typename T> inline void read(T &x)
{
    x=0;char c=getchar();bool flag=false;
    while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    if(flag)x=-x;
}
int n,m,k,dfn_cnt,co_cnt,top;
int dfn[maxn],low[maxn],co[maxn],st[maxn],a[maxn];
bool vis[maxn];
struct edge
{
    int to,nxt;
}e[maxn];
int head[maxn],edge_cnt;
void add(int from,int to)
{
    e[++edge_cnt]=(edge){to,head[from]};
    head[from]=edge_cnt;
}
void tarjan(int x)
{
    dfn[x]=low[x]=++dfn_cnt;
    st[++top]=x,vis[x]=true;
    for(int i=head[x];i;i=e[i].nxt)
    {
        int y=e[i].to;
        if(!dfn[y]) tarjan(y),low[x]=min(low[x],low[y]);
        else if(vis[y]) low[x]=min(low[x],dfn[y]);
    }
    if(low[x]==dfn[x])
    {
        co_cnt++;
        int now;
        do
        {
            now=st[top--];
            vis[now]=false;
            co[now]=co_cnt;
        }while(now!=x);
    }
}
bool check()
{
    for(int i=1;i<=4*n;++i)
        if(!dfn[i])
            tarjan(i);
    for(int i=1;i<=n;++i)
        if(co[p1(i)]==co[p0(i)]||co[pre1(i)]==co[pre0(i)])
            return false;
    return true;
}
int main()
{
    read(n),read(m),read(k);
    for(int i=1;i<=m;++i)
    {
        int x,y;
        read(x),read(y);
        add(p0(x),p1(y)),add(p0(y),p1(x));
    }
    for(int i=1;i<=k;++i)
    {
        int w;
        read(w);
        for(int j=1;j<=w;++j)
            read(a[j]),add(p1(a[j]),pre1(a[j])),add(pre0(a[j]),p0(a[j]));
        for(int j=2;j<=w;++j)
        {
            add(pre1(a[j-1]),pre1(a[j])),add(pre0(a[j]),pre0(a[j-1]));
            add(pre1(a[j-1]),p0(a[j])),add(p1(a[j]),pre0(a[j-1]));
        }
    }
    if(check()) puts("TAK");
    else puts("NIE");
    return 0;
}