首页 > 代码库 > BZOJ 3495: PA2010 Riddle
BZOJ 3495: PA2010 Riddle
Description
\(n\)个城市,\(k\)个国家,\(m\)条边，边两边至少有一个首都，问是否存在合法解。\(1\leqslant k\leqslant n,m\leqslant 10^6\)
Solution
2-SAT.
有几个限制条件一起列上...
这样建图是\(O(n^2)\)的...用前缀和表示来限制一下首都个数...
1.一个点不是首都，那么另一个点一定是首都.
2.前缀和为1，这个点一定为0.
3.这个点为1，前缀和一定为1.
4.这个点为1，前一个点一定为0.
5.这个位置的前缀和为0，前一个位置的前缀和一定为0.
6.这个位置的前缀和为1，后一个位置的前缀和一定为1.
然后缩点判断一下...用vector被卡常了...
Code
/************************************************************** Problem: 3495 User: BeiYu Language: C++ Result: Accepted Time:20436 ms Memory:350776 kb****************************************************************/ #include <bits/stdc++.h>using namespace std; const int N = 4000050;const int M = 20000050; inline int in(int x=0,char c=getchar()) { while(c>‘9‘||c<‘0‘) c=getchar(); while(c>=‘0‘&&c<=‘9‘) x=x*10+c-‘0‘,c=getchar();return x; } int n,k,m,cp,bp,tp;int a[N];int b[N],bl[N],dfn[N],low[N],stk[N]; int ep;int nxt[M],tto[M],hd[M]; void AddEdge(int fr,int to) { nxt[++ep]=hd[fr],tto[ep]=to,hd[fr]=ep; }void Tarjan(int u,int fa) { dfn[u]=low[u]=++cp,b[u]=1,stk[++tp]=u; for(int i=hd[u],v;i;i=nxt[i]) { v=tto[i]; if(!dfn[v]) Tarjan(v,u),low[u]=min(low[u],low[v]); else if(b[v]) low[u]=min(low[u],dfn[v]); } if(low[u]==dfn[u]) { for(bp++;;) { int v=stk[tp]; bl[v]=bp,b[v]=0,tp--; if(u==v) break; } }}int main() { n=in(),m=in(),k=in(); for(int i=1;i<=m;i++) { int u=in(),v=in(); AddEdge(u,v+n); AddEdge(v,u+n); } for(int i=1,t,j;i<=k;i++) { for(t=in(),j=1;j<=t;j++) a[j]=in(); for(j=1;j<=t;j++) { if(j+1<=t) AddEdge(a[j+1]+2*n,a[j]+2*n),AddEdge(a[j]+3*n,a[j+1]+3*n), AddEdge(a[j]+3*n,a[j+1]),AddEdge(a[j+1]+n,a[j]+2*n); AddEdge(a[j]+n,a[j]+3*n),AddEdge(a[j]+2*n,a[j]); } } for(int i=1;i<=4*n;i++) if(!dfn[i]) Tarjan(i,i); /* for(int i=1;i<=4*n;i++) { cout<<i<<" --> "; for(int j=0;j<(int)g[i].size();j++) cout<<g[i][j]<<" ";cout<<endl; } for(int i=1;i<=4*n;i++) cout<<dfn[i]<<" ";cout<<endl; for(int i=1;i<=4*n;i++) cout<<low[i]<<" ";cout<<endl; for(int i=1;i<=4*n;i++) cout<<bl[i]<<" ";cout<<endl;*/ for(int i=1;i<=n;i++) if(bl[i]==bl[i+n]) return puts("NIE"),0; for(int i=2*n+1;i<=3*n;i++) if(bl[i]==bl[i+n]) return puts("NIE"),0; return puts("TAK"),0;}
BZOJ 3495: PA2010 Riddle
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。