BZOJ3495 : PA2010 Riddle
2024-09-11 14:01:19
2-SAT。
建立n个变量,其中第i个变量表示第i个城市是否是首都。
对于边(x,y),连边x->y',y->x'。
对于一个有y个城市的国家,新建2y个变量,分别表示前i个城市和后i个城市中是否有首都。
然后求出SCC,判断是否存在合法的方案即可,时间复杂度$O(n+m)$。
#include<cstdio>
const int N=1000010,M=6000010;
int n,m,k,i,x,y,tot,f[N][2],pre[N][2],suf[N][2],q[M],t,from[M];bool v[M];
struct E{int v;E*nxt;}*g[M],*h[M],pool[N*24],*cur=pool,*p;
inline void add(int x,int y){
p=cur++;p->v=y;p->nxt=g[x];g[x]=p;
p=cur++;p->v=x;p->nxt=h[y];h[y]=p;
}
void dfs1(int x){
v[x]=1;
for(E*p=g[x];p;p=p->nxt)if(!v[p->v])dfs1(p->v);
q[++t]=x;
}
void dfs2(int x,int y){
v[x]=0,from[x]=y;
for(E*p=h[x];p;p=p->nxt)if(v[p->v])dfs2(p->v,y);
}
inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}
int main(){
read(n),read(m),read(k);
for(i=1;i<=n;i++)f[i][0]=++tot,f[i][1]=++tot;
while(m--)read(x),read(y),add(f[x][0],f[y][1]),add(f[y][0],f[x][1]);
while(k--){
read(y);
for(i=1;i<=y;i++){
pre[i][0]=++tot,pre[i][1]=++tot;
suf[i][0]=++tot,suf[i][1]=++tot;
read(x);
add(f[x][1],pre[i][1]);
add(f[x][1],suf[i][1]);
add(pre[i][0],f[x][0]);
add(suf[i][0],f[x][0]);
}
for(i=2;i<=y;i++){
add(pre[i-1][1],pre[i][1]);
add(pre[i-1][1],suf[i][0]);
add(pre[i-1][0],suf[i][1]);
add(suf[i][1],suf[i-1][1]);
add(suf[i][1],pre[i-1][0]);
add(suf[i][0],pre[i-1][1]);
}
}
for(i=1;i<=tot;i++)if(!v[i])dfs1(i);
for(i=tot;i;i--)if(v[q[i]])dfs2(q[i],q[i]);
for(i=1;i<n;i+=2)if(from[i]==from[i+1])return puts("NIE"),0;
return puts("TAK"),0;
}
最新文章
- 高性能JavaScript--数据存储(简要学习笔记二)
- BlueStacks 设置代理服务器 Proxifier指定任意程序的代理服务器
- nginx的rewrite,gzip,反向代理学习笔记
- Git教程之安装配置(1)
- Windows2003 下 MySQL 数据库每天自动备份
- URL 对特殊字符的处理
- tomcat虚拟主机虚拟目录配置
- UVA 10574 - Counting Rectangles(枚举+计数)
- ubuntu修改环境变量
- 使用.NET Core快速开发一个较正规的命令行应用程序
- JavaScript正则表达式模式匹配(4)——使用exec返回数组、捕获性分组和非捕获性分组、嵌套分组
- linux上查询网卡型号
- CentOS7.4+OpenStack-Queens版本部署
- 【C语言基础】什么是字节?
- mtr命令详解诊断网络路由
- spring boot 2.0.3+spring cloud (Finchley)1、搭建服务注册和发现组件Eureka 以及构建高可用Eureka Server集群
- iostat查看linux硬盘IO性能
- XPC connection interrupted
- Block(一)基础-b
- postgresql数据库uuid重复引发血案