bzoj3495 [PA2010]Riddle

2018-09-26 20:09:00


题意: $n$ 个城镇,分成了 $K$ 个国家,有 $m$ 条无向边连接这些城镇。要从每个国家中选一个作为首都,使得每条边的两个端点至少有一个是首都。


肥肠明显的 $2-SAT$ 问题

对于 $m$ 条给定的道路,连边 $u'→v$   $v'→u$

对于每个国家,只能有一个城镇是首都

但这样连边的复杂度是 $n^2$ 的

考虑优化建图

用 $u,u'$ 表示 $u$ 是否为首都

用 $U,U'$ 表示在 $u$ 所在国家中,以 $u$ 为结尾的前缀中是否有首都

先连边 $u'→v$   $v'→u$

然后可以发现存在三种关系:

  • $u→U$   $U'→u'$

  • $pre(U)→U$   $U'→pre(U)'$

  • $u→pre(U)'$   $pre(U)→u'$

这样就把建图的复杂度优化为 $O(n+m)$

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define reg register
using namespace std;
const int N=6e6+6;
struct node
{
    int to,nxt;
}edge[N<<1];
int n,m,T,num,cnt,flag,head[N];
int dfn[N],low[N],stack[N],bel[N],top,tim,tot;
bool exist[N];
inline int read()
{
    int x=0,w=1;
    char c=getchar();
    while (!isdigit(c)&&c!='-') c=getchar();
    if (c=='-') c=getchar(),w=-1;
    while (isdigit(c))
    {
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar();
    }
    return x*w;
}
inline void add_edge(int from,int to)
{
    edge[++num]=(node){to,head[from]};
    head[from]=num;
}
void tarjan(int k)
{
    int temp;
    dfn[k]=low[k]=++tim;
    stack[++top]=k; exist[k]=1;
    for (reg int i=head[k];i;i=edge[i].nxt)
    {
        int v=edge[i].to;
        if (!dfn[v])
        {
            tarjan(v);
            low[k]=min(low[k],low[v]);
        }
        else if (exist[v])
          low[k]=min(low[k],dfn[v]);
    }
    if (dfn[k]==low[k])
    {
        ++tot;
        do
        {
            temp=stack[top--];
            exist[temp]=0;
            bel[temp]=tot;
        }while (temp!=k);
    }
}
int main()
{
    cnt=n=read(),m=read(),T=read();
    for (reg int i=1;i<=m;i++)
    {
        int x=read(),y=read();
        add_edge(x<<1|1,y<<1);
        add_edge(y<<1|1,x<<1);
    }
    while (T--)
    {
        int S=read();
        for (reg int i=1;i<=S;i++)
        {
            int x=read(),y=cnt+i;
            if (i>1)
            {
                add_edge((y-1)<<1,y<<1); add_edge(y<<1|1,(y-1)<<1|1);
                add_edge(x<<1,(y-1)<<1|1); add_edge((y-1)<<1,x<<1|1);
            }
            add_edge(x<<1,y<<1); add_edge(y<<1|1,x<<1|1);
        }
        cnt+=(S<<1);
    }
    for (reg int i=1;i<=(cnt<<1|1);i++) if (!dfn[i]) tarjan(i);
    for (reg int i=1;i<=cnt;i++)
      if (bel[i<<1]==bel[i<<1|1]) {flag=1; break;}
    if (flag) puts("NIE"); else puts("TAK");
    return 0;
}