BZOJ2649 : riddle

riddle"/>

BZOJ2649 : riddle

题意同3495，但是内存限制收紧了，不能采用3495的前后缀优化建图的方式。

注意到“每个集合恰好选择一个点”可以放宽成“每个集合最多选择一个点”，对于最后求出的方案里，如果某个集合没选点，任选一个就好了。

考虑2-SAT建图，有两类边：

1. 对于每条给定的边$(u,v)$：如果不选$u$就必须选$v$，如果不选$v$就必须选$u$。

2. 对于每个集合：如果选了一个点就不能选其它所有点。

第二类边不能直接建图，但是在Kosaraju算法中DFS图的时候，每个点$x$和$x$所在集合内除了$x$之外的所有点都连了一条第二类边，需要用一个数据结构跳过那些已经搜过的且不是$x$的点。用一个支持双端pop的队列维护就可以了，如果这个集合不是只剩$x$没搜过，那么两端至少可以消费一个点。

时间复杂度$O(n+m+k)$。

#include<cstdio>
const int N=2000010,M=1000010,BUF=25000000;
char Buf[BUF],*buf=Buf;
int n,m,K,o,i,j,x,y,S[M],T[M],st[M],en[M],pool[M],tot,at[M];
int e[M][2],g[N],v[N],nxt[N],ed;
int q[N],t,f[N];
bool vis[N];
inline void read(int&a){for(a=0;*buf<48;buf++);while(*buf>47)a=a*10+*buf++-48;}
inline void add(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}
void dfs1(int x){if(vis[x])return;vis[x]=1;for(int i=g[x];i;i=nxt[i])dfs1(v[i]);if(x>n)while(S[at[x-n]]<=T[at[x-n]]){if(pool[S[at[x-n]]]!=x-n)dfs1(pool[S[at[x-n]]++]);else if(pool[T[at[x-n]]]!=x-n)dfs1(pool[T[at[x-n]]--]);else break;}q[++t]=x;
}
void dfs2(int x){if(!vis[x])return;vis[x]=0,f[x]=o;for(int i=g[x];i;i=nxt[i])dfs2(v[i]);if(x<=n)while(S[at[x]]<=T[at[x]]){if(pool[S[at[x]]]!=x)dfs2(pool[S[at[x]]++]+n);else if(pool[T[at[x]]]!=x)dfs2(pool[T[at[x]]--]+n);else break;}
}
int main(){fread(Buf,1,BUF,stdin);read(n),read(m),read(K);for(i=1;i<=m;i++){read(x),read(y);e[i][0]=x,e[i][1]=y;add(x,y+n),add(y,x+n);}for(i=1;i<=K;i++){read(y);st[i]=tot+1;while(y--){read(x);at[x]=i;pool[++tot]=x;}en[i]=tot;}for(i=1;i<=K;i++)S[i]=st[i],T[i]=en[i];for(i=1;i<=n+n;i++)if(!vis[i])dfs1(i);for(ed=0,i=1;i<=n+n;i++)g[i]=0;for(i=1;i<=m;i++){x=e[i][0],y=e[i][1];add(y+n,x),add(x+n,y);}for(i=1;i<=K;i++)S[i]=st[i],T[i]=en[i];for(i=t;i;i--)if(vis[q[i]])o++,dfs2(q[i]);for(i=1;i<=n;i++)if(f[i]==f[i+n])return puts("NIE"),0;puts("TAK");for(i=1;i<=K;i++)st[i]=pool[st[i]];for(i=1;i<=n;i++)if(f[i]<f[i+n])st[at[i]]=i;for(i=1;i<=K;i++)printf("%d ",st[i]);return 0;
}

转载于:.html