bzoj 3495 PA2010 Riddle

bzoj 3495 PA2010 Riddle

​​ 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 HINT

Source 鸣谢onion_cyc提供翻译

感觉自己太菜了为了这点东西调试一下午

考虑暴力n^2建边很好想 那GG做不了怎么办 优化建图即

设s[i]表示在当前这个郡里 我现在前i个中是否存在首都s[i][0]不存在s[i][1]存在

然后那么有连边方式设u’为u的反面点其他字母同理

有关联的两边u->v’ v->u’

x->pre[i-1]’ pre[i-1]->x’

x->pre[i] pre[i]’->x’

pre[i-1]->pre[i] pre[i]’->pre[i-1]’

其实这样也是有情况会有问题的 不符合我们建图的初衷但是i只要求输出TAKNIE 所以因为题目的特殊限制即 一条边两边至少有一个是首都 o所以这样跑出来是对的

#include#include#includeusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f;}const int N=4e6+10;struct node{ int y,next;}data[N<<1];bool stackf[N];int h[N],cnt,num,q[N],id[N>>2],s,b[N],low[N],dfn[N],top,m,k,n;inline void insert1(int x,int y){ data[++num].y=y;data[num].next=h[x];h[x]=num;}inline void tarjan(int x){ dfn[x]=low[x]=++num;stackf[x]=1;q[++top]=x; for (int i=h[x];i;i=data[i].next){ int y=data[i].y; if (!dfn[y]) tarjan(y),low[x]=min(low[x],low[y]);else if(stackf[y]) low[x]=min(low[x],dfn[y]); } if(low[x]==dfn[x]){ int y;++s; do{ y=q[top--];stackf[y]=0;b[y]=s; }while(y!=x); }}int main(){ //freopen("bzoj3495.in","r",stdin); n=read();m=read();k=read(); for (int i=1;i<=n;++i) cnt+=2,id[i]=cnt; for (int i=1;i<=m;++i){ int x=read(),y=read(); insert1(id[x]^1,id[y]);insert1(id[y]^1,id[x]); } for (int owo=1;owo<=k;++owo){ int t=read(),x=read(),lst=(cnt+=2); insert1(id[x],cnt);insert1(cnt^1,id[x]^1); for (int i=2;i<=t;++i){ x=read();cnt+=2; insert1(id[x],cnt);insert1(cnt^1,id[x]^1); insert1(id[x],lst^1);insert1(lst,id[x]^1); insert1(lst,cnt);insert1(cnt^1,lst^1);lst=cnt; } }num=0;bool flag=0; for(int i=2;i<=cnt;++i) if (!dfn[i]) tarjan(i); for (int i=1;i<=n;++i) if (b[id[i]]==b[id[i]^1]) {flag=1;break;} if (flag) puts("NIE");else puts("TAK"); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。