bzoj3495 [PA2010]Riddle

题意：$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; } ```