[BZOJ 1997][HNOI2010]Planar(2-SAT)

时间：2022-09-06 11:49:00

题目：http://www.lydsy.com:808/JudgeOnline/problem.php?id=1997

分析：

考虑每条边是在圈子里面还是圈子外面

所以就变成了2-SAT判定问题了= =，于是求SCC，如果一个点对应的2个bool点在一个SCC中就无解了。

当然这样建图好像要TLE……

然后就要上大杀器了：平面图|E|<=3|V|-6

所以，如果m>3n-6就直接输出NO了

[BZOJ 1997][HNOI2010]Planar(2-SAT)的更多相关文章

  1. BZOJ 1997&colon; &lbrack;Hnoi2010&rsqb;Planar&lpar; 2sat &rpar;

    平面图中E ≤ V*2-6.. 一个圈上2个点的边可以是在外或者内, 经典的2sat问题.. ----------------------------------------------------- ...

  2. Bzoj 1997 &lbrack;Hnoi2010&rsqb;Planar题解

    1997: [Hnoi2010]Planar Time Limit: 10 Sec  Memory Limit: 64 MBSubmit: 2224  Solved: 824[Submit][Stat ...

  3. bzoj 1997 &lbrack;Hnoi2010&rsqb;Planar——2-SAT&plus;平面图的一个定理

    题目:https://www.lydsy.com/JudgeOnline/problem.php?id=1997 平面图的一个定理:若边数大于(3*点数-6),则该图不是平面图. 然后就可以2-SAT ...

  4. bzoj 1997&colon; &lbrack;Hnoi2010&rsqb;Planar

    #include<cstdio> #include<cstring> #include<iostream> #define M 20005 #define N 20 ...

  5. bzoj 1997&colon; &lbrack;Hnoi2010&rsqb;Planar【瞎搞&plus;黑白染色】

    脑补一下给出的图:一个环,然后有若干连接环点的边,我们就是要求这些边不重叠 考虑一下不重叠的情况,两个有交边一定要一个在环内一个在环外,所以把相交的边连边,然后跑黑白染色看是否能不矛盾即可(可能算个2 ...

  6. 1997&colon; &lbrack;Hnoi2010&rsqb;Planar

    1997: [Hnoi2010]Planar 链接 分析: 首先在给定的那个环上考虑进行操作,如果环内有有两条边相交,那么可以把其中的一条放到环的外面去.所以转换为2-sat问题. 像这样,由于1-4 ...

  7. bzoj千题计划231：bzoj1997&colon; &lbrack;Hnoi2010&rsqb;Planar

    http://www.lydsy.com/JudgeOnline/problem.php?id=1997 如果两条边在环内相交,那么一定也在环外相交 所以环内相交的两条边,必须一条在环内,一条在环外 ...

  8. &lbrack;bzoj1997&rsqb;&lbrack;Hnoi2010&rsqb;Planar&lpar;2-sat&vert;&vert;括号序列&rpar;

    开始填连通分量的大坑了= = 然后平面图有个性质m<=3*n-6..... 由平面图的欧拉定理n-m+r=2(r为平面图的面的个数),在极大平面图的情况可以代入得到m=3*n-6. 网上的证明( ...

  9. 条件转化，2-sat BZOJ 1997

    http://www.lydsy.com/JudgeOnline/problem.php?id=1997 1997: [Hnoi2010]Planar Time Limit: 10 Sec  Memo ...

随机推荐

  1. 一条SQL查询MYSQL最大内存用量

    // max_mem_usage

  2. 全局变量 urllib模块 json模块

    1.vars()  查看一个.py文件中的全局变量 print(vars()) #重点 __name__': '__main__ '__file__': 'C:/Users/lenovo/Pychar ...

  3. PHP array&lowbar;chunk&lpar;&rpar; 函数

    今天在CSDN上,看到了一个问题 一维数组 PHP code   array('0'=>'a',1=>'b',2=>'c',3=>'d',4=>'e',5=>'f' ...

  4. Linux 软件包安装管理

    转自:http://www.cnblogs.com/Quains/archive/2012/01/03/2311049.html 本文主要是记录下RedHat系列的软件包管理. 内容分为以下三个部分: ...

  5. 『OGG 01』Win7 配置 Oracle GoldenGate 踩坑指南

    安装 Oracle 安装 Oracle11g 32位[Oracle 32位的话,OGG 也必须是 32位,否则会有0xc000007b无法正常启动 错误] 安装目录为 D:\oracle\produc ...

  6. Linux 故障问题处理

    一.   Debian   网卡问题 原因: 网卡提示 Device Not Managed 处理方法: . 编辑/etc/NetworkManager/NetworkManager.conf: 将其 ...

  7. REST-framework快速构建API--生成Swagger接口文档

    一.Swagger概述 1.引言 当接口开发完成,紧接着需要编写接口文档.传统的接口文档使用Word编写,or一些接口文档管理平台进行编写,但此类接口文档维护更新比较麻烦,每次接口有变更,需要手动修改 ...

  8. 【Mongodb】用户和认证 权限总结

    开启MongoDB服务时不添加任何参数时,默认是没有权限验证的,登录的用户可以对数据库任意操作而且可以远程访问数据库!   在刚安装完毕的时候MongoDB都默认有一个admin数据库,此时admin ...

  9. 阿里云CentOS7挂载SSD云盘的方法

    https://bbs.aliyun.com/read/151152.html 阿里云购买的第2块云盘默认是不自动挂载的,需要手动配置挂载上. 1.查看SSD云盘 sudo fdisk -l Disk ...

  10. Lost connection to MySQL server during query &lpar;&lbrack;Errno 104&rsqb; Connection reset by peer&rpar;

    Can't connect to MySQL server Lost connection to MySQL server during query · Issue #269 · PyMySQL/Py ...

相关文章