BZOJ 3495: PA2010 Riddle 2-SAT：前缀优化建图titleanalysiscode

title

BZOJ 3495
Description

有n个城镇被分成了k个郡，有m条连接城镇的无向边。
要求给每个郡选择一个城镇作为首都，满足每条边至少有一个端点是首都。

Input

第一行有三个整数，城镇数n（(1le nle10^6)），边数m（(0le mle10^6)），郡数k（1<=k<=n）。
接下来m行，每行有两个整数ai和bi（ai≠bi），表示有一条无向边连接城镇ai和bi。
接下来k行，第j行以一个整数wj开头，后面是wj个整数，表示第j个郡包含的城镇。

Output

若有解输出TAK，否则输出NIE。

Sample Input

6 5 2
1 2
3 1
1 4
5 2
6 2
3 3 4 2
3 1 6 5

Sample Output

TAK

Source

鸣谢onion_cyc提供翻译

analysis

(2-SAT) 很容易看出来，关键在于怎么保证每个国家只能有一个首都。

也就是如果某一个选了，就会有后面的不能选，前面的也不能选的关系，但是边数是 (n^2) 的，难以接受。

所以就需要一个小技巧了：前缀优化建图。

细节方面见参考资料：Rising_shit 。

其实我是觉得 HYJ_cnyali 的方法更好，也很容易理解。

code

#include<bits/stdc++.h>
using namespace std;
const int maxn=3e6+10;
char buf[1<<15],*fs,*ft;
inline char getc() { return (ft==fs&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),ft==fs))?0:*fs++; }
template<typename T>inline void read(T &x)
{
x=0;
T f=1, ch=getchar();
while (!isdigit(ch) && ch^'-') ch=getchar();
if (ch=='-') f=-1, ch=getchar();
while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48), ch=getchar();
x*=f;
}
template<typename T>inline void write(T x)
{
if (!x) { putchar('0'); return ; }
if (x<0) putchar('-'), x=-x;
T num=0, ch[20];
while (x) ch[++num]=x%10+48, x/=10;
while (num) putchar(ch[num--]);
}
int ver[maxn*6],Next[maxn*6],head[maxn<<1],len=1;
inline void add(int x,int y)
{
ver[++len]=y,Next[len]=head[x],head[x]=len;
}
int dfn[maxn<<1],low[maxn<<1],id;
int Stack[maxn<<1],top;
int belong[maxn<<1],tot;
bool instack[maxn<<1];
inline void tarjan(int x)
{
dfn[x]=low[x]=++id;
Stack[++top]=x;
instack[x]=1;
for (int i=head[x]; i; i=Next[i])
{
int y=ver[i];
if (!dfn[y])
{
tarjan(y);
low[x]=min(low[x],low[y]);
}
else if (instack[y])
low[x]=min(low[x],dfn[y]);
}
if (low[x]==dfn[x])
{
int k;
++tot;
do
{
k=Stack[top--];
belong[k]=tot;
instack[k]=0;
} while (k!=x);
}
}
int pre[maxn];
int main()
{
memset(pre,-1,sizeof(pre));
int n,m,k;read(n);read(m);read(k);
for (int i=1,x,y; i<=m; ++i) read(x),read(y),--x,--y,add(y<<2|1,x<<2),add(x<<2|1,y<<2);
for (int i=1,w,last; i<=k; ++i)
{
read(w);read(last);--last;
for (int j=1,y; j<w; ++j) read(y),--y,pre[y]=last,last=y;
}
for (int i=0; i<n; ++i)//前缀优化建图
{
int x1=i<<2,x2=x1|1,x3=x2+1,x4=x3+1;
add(x1,x3),add(x4,x2);
if (pre[i]!=-1)
{
int j=pre[i],y1=j<<2,y2=y1|1,y3=y2+1,y4=y3+1;
add(y3,x3),add(x4,y4),add(y3,x2),add(x1,y4);
}
}
for (int i=0; i<(n<<1); ++i)
if (!dfn[i]) tarjan(i);
for (int i=0; i<(n<<1); ++i)
if (belong[i]==belong[i^1]) return puts("NIE"),0;
puts("TAK");
return 0;
}