题目
Description
有n个城镇被分成了k个郡，有m条连接城镇的无向边。
要求给每个郡选择一个城镇作为首都，满足每条边至少有一个端点是首都。
Input
第一行有三个整数，城镇数n（1<=n<=10^6），边数m（0<=m<=10^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
题解
发现有两种限制，边的限制可以转换成两个条件二选一，关键是首都的限制怎么搞
有一种神奇的优化建图方式，前（后）缀优化建图
对于一个郡，点$p_x$表示$x$前面的点（包括$x$）有选作首都的了，同时建出反点$p_x’$表示没有选作首都的点
同时$d_x$表示选择这个点当首都，$d_x’$表示不选
这样的话就有以下关系了：
边$(u,v)$：$d_u’\rightarrow d_v,d_v’\rightarrow d_u$
$d_x\rightarrow p_x,p_x’\rightarrow d_x’$
$p_{x-1}\rightarrow p_x,p_x’\rightarrow p_{x-1}’$
$d_x\rightarrow p_{x-1}’,p_{x-1}\rightarrow d_x’$
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
# define A(x) (x)
# define B(x) (x+n)
# define C(x) (x+2*n)
# define D(x) (x+3*n)
using namespace std;
const int MAX=5e6+5;
struct p{
int x,y;
}c[MAX<<1];
int n,m,num,Top,cnt,K,_;
int h[MAX],dfn[MAX],low[MAX],st[MAX],col[MAX],a[MAX];
bool use[MAX];
void add(int x,int y) {c[++num]=(p){h[x],y},h[x]=num;}
void Tarjan(int x)
{
st[++Top]=x,use[x]=1,dfn[x]=low[x]=++cnt;
for(int i=h[x];i;i=c[i].x)
if(!dfn[c[i].y]) Tarjan(c[i].y),low[x]=min(low[x],low[c[i].y]);
else if(use[c[i].y]) low[x]=min(low[x],dfn[c[i].y]);
if(dfn[x]==low[x])
{
int tt=-1;
++_;
while(tt!=x) tt=st[Top--],use[tt]=0,col[tt]=_;
}
}
int read()
{
int x(0);
char ch=getchar();
for(;!isdigit(ch);ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x;
}
int main()
{
n=read(),m=read(),K=read();
for(int i=1,x,y;i<=m;++i)
x=read(),y=read(),add(B(x),A(y)),add(B(y),A(x));
for(int i=1;i<=n;++i)
add(A(i),C(i)),add(D(i),B(i));
for(int i=1,tt;i<=K;++i)
{
tt=read();
for(int j=1;j<=tt;++j)
{
a[j]=read();
if(j>1) add(A(a[j]),D(a[j-1])),add(C(a[j-1]),B(a[j])),add(C(a[j-1]),C(a[j])),add(D(a[j]),D(a[j-1]));
}
}
for(int i=1;i<=4*n;++i)
if(!dfn[i]) Tarjan(i);
for(int i=1;i<=n;++i)
if(col[A(i)]==col[B(i)]||col[C(i)]==col[D(i)]) return printf("NIE"),0;
return printf("TAK"),0;
}
