【BZOJ3495】PA2010 Riddle

2016.03.24 08:53 Thu | 41次阅读 | 旧日oi | 固定链接 | 源码

题解

2-SAT

每个城市 只有是首都或不是,考虑2-SAT。
对于给出的边,我们可以直接连不选u就必选v的边。
而对于每个国家只能选一个的限制,我们可以这么考虑,如果选第i个点,那么这个国家i之前和之后的点都不能选,我们新建一些点表示这个国家的点的前缀和和后缀和就可以了。以前缀和为例,pre[i]只需和pre[i-1]和第i个点连边就可以了。如何保证每个国家必选一个点呢?连pre[i]和suf[i+1]就可以了。

mycode

#include <bits/stdc++.h>
using namespace std;
#define N 1000005
int k,n,m,tot;
int h[N*8],tp=1;
struct edge{int to,next;}e[N*15];
void ae(int u,int v){e[++tp].to=v;e[tp].next=h[u];h[u]=tp;}
int pre[N],suf[N];
int st[N*8],dfn[N*8],low[N*8],scc[N*8],top,tim,cnt;
void dfs(int u)
{
    low[u]=dfn[u]=++tim;st[++top]=u;
    for(int v,i=h[u];i;i=e[i].next)
    {
        if(!dfn[v=e[i].to])
        {
            dfs(v);
            low[u]=min(low[u],low[v]);
        }
        else if(!scc[v]) low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u])
    {
        int x=-1;cnt++;
        while(x!=u) scc[x=st[top--]]=cnt;
    }
}
char getc(){
    static char *S,*T,buf[65536];
    if(S==T){T=(S=buf)+fread(buf,1,65536,stdin);if(S==T) return EOF;}
    return *S++;
}
int read(){
    static char ch;static int D;
    while(!isdigit(ch=getc()));
    for(D=ch-'0';isdigit(ch=getc());) D=D*10+ch-'0';
    return D;
}
int main()
{
    k=read();m=read();n=read();
    for(int u,v,i=1;i<=m;i++)
    {
        u=(read()-1)<<1;v=(read()-1)<<1;
        ae(u^1,v);ae(v^1,u);
    }
    int tot=k-1;
    for(int d,i=1;i<=n;i++)
    {
        d=read();
        for(int x,j=1;j<=d;j++)
        {
            x=(read()-1)<<1;
            pre[j]=(++tot)<<1;
            suf[j]=(++tot)<<1;
            ae(x,pre[j]);
            ae(x,suf[j]);
            ae(pre[j]^1,x^1);
            ae(suf[j]^1,x^1);
        }
        for(int j=2;j<=d;j++)
        {
            ae(pre[j-1],pre[j]);
            ae(pre[j]^1,pre[j-1]^1);
            ae(pre[j-1],suf[j]^1);
            ae(pre[j-1]^1,suf[j]);
            ae(suf[j],suf[j-1]);
            ae(suf[j-1]^1,suf[j]^1);
            ae(suf[j],pre[j-1]^1);
            ae(suf[j]^1,pre[j-1]);
        }
    }
    for(int i=0;i<=(tot<<1);i++)
    if(!dfn[i]) dfs(i);
    for(int i=0;i<=tot;i++)
    if(scc[i<<1]==scc[i<<1|1])
    {
        puts("NIE");
        return 0;
    }
    puts("TAK");
}