【BZOJ】3495: PA2010 Riddle 2-SAT算法
2024-09-01 15:49:43
【题意】有n个城镇被分成了k个郡,有m条连接城镇的无向边。要求给每个郡选择一个城镇作为首都,满足每条边至少有一个端点是首都。n,m,k<=10^6。
【算法】2-SAT,前后缀优化建图
【题解】每个城镇只有作为首都和不是首都两种选项,即2-sat问题。
2-sat问题中所有边必须加反向边,下面过程忽略反向边。
对于一条边(x,y),如果x是0,那么y必须是1,即x-y'。(y-x'是反向边,考虑的时候忽略)
但是一个郡只有一个首都有点烦,有一种套路叫前后缀优化建图。
对于每个点x,假设一个点x+n,表示编号<=x的和x同在一个郡的点中是否有首都。
假设x和y是同一个郡的相邻编号点(y>x),那么:
1.前缀:(x+n)' - (y+n)'
2.修改:x' - (x+n)'
3.只有一个首都:(x+n)' - y
所以n*4个点和n*8条边,进行2-sat。
复杂度O(M),M=(m+3*n)*2。
#include<cctype>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int read(){
int s=,t=;char c;
while(!isdigit(c=getchar()))if(c=='-')t=-;
do{s=s*+c-'';}while(isdigit(c=getchar()));
return s*t;
}
const int maxn=;
int n,m,K,first[maxn],tot,c,B[],C[];
bool mark[maxn];
struct edge{int v,from;}e[maxn*];////
void insert(int u,int v){
tot++;e[tot].v=v;e[tot].from=first[u];first[u]=tot;
tot++;e[tot].v=u^;e[tot].from=first[v^];first[v^]=tot;
}
int dfsnum=,TOT,top,dfn[maxn],low[maxn],st[maxn],belong[maxn];
void tarjan(int x){
dfn[x]=low[x]=++dfsnum;
st[++top]=x;
for(int i=first[x];i;i=e[i].from)if(!dfn[e[i].v]){
tarjan(e[i].v);
low[x]=min(low[x],low[e[i].v]);
}else if(!belong[e[i].v])low[x]=min(low[x],dfn[e[i].v]);
if(low[x]==dfn[x]){
TOT++;
while(st[top]!=x)belong[st[top--]]=TOT;
belong[st[top--]]=TOT;
}
}
int main(){
n=read();m=read();K=read();
for(int i=;i<=m;i++){
int u=read()-,v=read()-;
insert(u<<,v<<|);
}
for(int i=;i<n;i++)insert(i<<|,(i+n)<<|);///
for(int k=;k<=K;k++){
int w=read(),p,pre=read()-;B[pre]=k;
for(int i=;i<=w;pre=p,i++){
p=read()-;B[p]=k;
insert((pre+n)<<|,(p+n)<<|);
insert((pre+n)<<|,p<<);
}
}
for(int i=;i<n*;i+=){
if(!dfn[i])tarjan(i);
if(!dfn[i^])tarjan(i^);
if(belong[i]==belong[i^]){printf("NIE");return ;}
}
printf("TAK");
return ;
}
从这道题开始,我知道了一件事:理论复杂度O(nm)的DFS版2-sat是可以无视随机被卡TLE的。
嘤嘤嘤T_T。
最新文章
- ASP.NET基础代码备忘
- docker 私有镜像管理工具harbor 安装
- 由后序遍历结果构造二叉查找树 &;&; 二叉查找树链表化
- 基于 HTML5 的数据存储
- 【原创】一起学C++ 之->;(箭头符号) ---------C++ primer plus(第6版)
- [Design Pattern] Facde Pattern 简单案例
- Maximum Subarray (JAVA)
- Servlet的运行方式
- HDU1342 Lotto 【深搜】
- winscp工具和xshell连接linux机器时切换到root账户
- python day07笔记总结
- 让我头疼一下午的Excel合并单元格
- oracle 学习day01
- 嵌入式开发之hi3519---spi nor flash启动
- vee-validate 中文配置报错及自定义规则 报错.updateDictionary/.addlocale is not a function
- wpf ,只能窗口调整高度,并且设定最小值。
- VS2012 常用配置
- django之jquery完成ajax
- HDU2588
- openwrt(二) 配置openwrt及编译
热门文章
- lintcode-383-装最多水的容器
- C++ Primer Plus学习:第九章
- OSG学习:阴影代码示例
- jdbc 2.0
- 6/2 sprint2 看板和燃尽图的更新
- 使用vue的mixins混入实现对正在编辑的页面离开时提示
- hdu mophues
- stm32f4xx系统总线架构
- 【转载】Java中的锁机制 synchronized &; 偏向锁 &; 轻量级锁 &; 重量级锁 &; 各自优缺点及场景 &; AtomicReference
- Frequent values UVA - 11235(巧妙地RMQ)