Bzoj 1997 [Hnoi2010]Planar题解
2024-09-01 02:41:44
1997: [Hnoi2010]Planar
Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 2224 Solved: 824
[Submit][Status][Discuss]
Description
Input
Output
Sample Input
2
6 9
1 4
1 5
1 6
2 4
2 5
2 6
3 4
3 5
3 6
1 4 2 5 3 6
5 5
1 2
2 3
3 4
4 5
5 1
1 2 3 4 5
6 9
1 4
1 5
1 6
2 4
2 5
2 6
3 4
3 5
3 6
1 4 2 5 3 6
5 5
1 2
2 3
3 4
4 5
5 1
1 2 3 4 5
Sample Output
NO
YES
YES
HINT
Source
为了做这道题我生生看了大半个小时的各种不靠谱的平面图课件,然后题解告诉我平面图的性质就用到了m>n*3-6不是平面图而且他只是用来剪枝的?Exucse me?
然后又发现这道题是2-SAT,一个坑了几乎所有NOI2017选手的知识点,然后又斯巴达了一个多小时的2-SAT,回过头来却发现我连如何判断两条边是否会相交都不懂。QAQ……
然后赶紧向大佬求助,既然这道题把环都给我们了,那么只要两个线段的四个端点是交错排列的那么他们如果把它们同时放在圆内或圆外他们就会相交。这也就是为什么要用2-SAT了。我们可以把它看作2-SAT的一个经典问题:n各组,每组两个人,其中有些人和别的组里的人不能一起选,每个组里必须选一个人,问能否找到合法方案。在这道题里,每一个不在圆上的线段就是我们的组,两个人就是在圆内还是圆外,跑一遍2-SAT即可。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<string>
#include<queue>
#define N 300
using namespace std;
struct ro{
int to;
int next;
}road[**];
int t,n,m,zz,a[],f[][],pos[N],zz1;
void build(int x,int y)
{
zz++;
road[zz].to=y;
road[zz].next=a[x];
a[x]=zz;
}
int dfn[],low[],zz2,top,st[],bel[],zz3;
bool rd[],rd2[];
void tar(int x)
{
zz2++;
dfn[x]=low[x]=zz2;
top++;
st[top]=x;
rd[x]=rd2[x]=;
for(int i=a[x];i>;i=road[i].next)
{
int y=road[i].to;
if(!rd2[y])
{
tar(y);
low[x]=min(low[x],low[y]);
}
else if(rd[y])
{
low[x]=min(dfn[y],low[x]);
}
}
if(dfn[x]==low[x])
{
zz3++;
int v;
do{
v=st[top];
top--;
rd[v]=;
bel[v]=zz3;
}while(dfn[v]!=low[v]);
}
}
int main(){
scanf("%d",&t);
while(t--)
{
memset(a,,sizeof(a));
top=;
memset(rd2,,sizeof(rd2));
zz3=zz2=;
memset(low,,sizeof(low));
memset(dfn,,sizeof(dfn));
zz=zz1=;
memset(bel,,sizeof(bel));
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)
{
scanf("%d%d",&f[i][],&f[i][]);
}
for(int i=;i<=n;i++)
{
int x;
scanf("%d",&x);
pos[x]=i;
}
if(n*-<m)
{
printf("NO\n");
continue;
}
for(int i=;i<=m;i++)
{
int fr=f[i][],to=f[i][];
fr=pos[fr],to=pos[to];
if(fr>to)swap(fr,to);
if(to-fr==||(to==n&&fr==))continue;
zz1++;
f[zz1][]=fr,f[zz1][]=to;
}
m=zz1;
for(int i=;i<=m;i++)
{
for(int j=i+;j<=m;j++)
{
if(f[i][]<f[j][]&&f[i][]<f[j][]&&f[i][]>f[j][])
{
build(i*,j*-);
build(j*-,i*);
build(j*,i*-);
build(i*-,j*);
}
else if(f[j][]<f[i][]&&f[j][]<f[i][]&&f[i][]<f[j][])
{
build(i*,j*-);
build(j*-,i*);
build(j*,i*-);
build(i*-,j*);
}
}
}
for(int i=;i<=*m;i++)
{
if(!rd2[i])
{
tar(i);
}
}
bool yx=;
for(int i=;i<=m;i++)
{
if(bel[i*]==bel[i*-])
{
yx=;
break;
}
}
if(yx)
{
printf("YES\n");
}
else
{
printf("NO\n");
}
}
return ;
}
最新文章
- Ueditor 增加模板
- Trianglify - 生成五彩缤纷的 SVG 背景图案
- java与微信企业号交互
- cocos在win平台exe无法使用 UserDefault 解决方法
- css3文字导航鼠标悬停气泡动画特效源码下载
- Hibernate-org.hibernate.QueryException: could not resolve property: code of:
- Oracle 将普通表转换为分区表
- systemd service
- WPF中的MatrixTransform
- 使用Linux的命令行工具做简单的文本分析
- spring mvc 复杂参数注入
- 前台js根据当前时间生成订单号
- python中的is和==
- 卖给高通之后的CSR的现状和未来
- matplotlib绘图
- 电商系统架构总结1(EF)
- ActivityGroup实现tab功能
- POJ 3352 Road Construction 双联通分量 难度:1
- unity update与fixedUpdate
- java代码-------多线程实例
热门文章
- 浅析在QtWidget中自定义Model(beginInsertRows()和endInsertRows()是空架子,类似于一种信号,用来通知底层)
- phpstudy+phpstorm+debug
- Qt的模态对话框和非模态对话框 经常使用setAttribute (Qt::WA_DeleteOnClose)
- qt实现-给SQLITE添加自定义函数(对某个字段进行加密)
- win7访问部分win2003速度慢
- Hadoop集群(第6期)JDK和SSH无密码配置
- c++ LeetCode (初级字符串篇) 九道算法例题代码详解(二)
- python列表的内建函数
- Django学习笔记(20)——BBS+Blog项目开发(4)Django如何使用Bootstrap
- 简单有趣的hover