P1444 [USACO1.3]虫洞wormhole
发布日期:2022-02-22 18:04:13 浏览次数:11 分类:技术文章

本文共 1853 字,大约阅读时间需要 6 分钟。

luogu P1444 [USACO1.3]虫洞wormhole

首先感谢ghj的讲解

题目描述

农夫约翰爱好在周末进行高能物理实验的结果却适得其反,导致N个虫洞在农场上(2<=N<=12,n是偶数),每个在农场二维地图的一个不同点。

根据他的计算,约翰知道他的虫洞将形成 N/2 连接配对。例如,如果A和B的虫洞连接成一对,进入虫洞A的任何对象体将从虫洞B出去,朝着同一个方向,而且进入虫洞B的任何对象将同样从虫洞A出去,朝着相同的方向前进。这可能发生相当令人不快的后果。

例如,假设有两个成对的虫洞A(1,1) 和 B(3,1),贝茜从(2,1)开始朝着 +x 方向(右)的位置移动。贝茜将进入虫洞 B(在(3,1)),从A出去(在(1,1)),然后再次进入B,困在一个无限循环中!

| . . . .| A > B .      贝茜会穿过B,A,+ . . . .      然后再次穿过B

农夫约翰知道他的农场里每个虫洞的确切位置。他知道贝茜总是向 +x 方向走进来,虽然他不记得贝茜的当前位置。请帮助农夫约翰计算不同的虫洞配对(情况),使贝茜可能被困在一个无限循环中,如果她从不幸的位置开始。

输入输出格式

输入格式:

第1行:N(N<=12),虫洞的数目

第2到N+1行:每一行都包含两个空格分隔的整数,描述一个以(x,y)为坐标的单一的虫洞。每个坐标是在范围 0-1000000000。

输出格式:

第1行:会使贝茜从某个起始点出发沿+x方向移动卡在循环中的不同的配对

输入输出样例

输入样例#1:

40 01 01 10 1

输出样例#1:

2

说明

如果我们将虫洞编号为1到4,然后通过匹配 1 与 2 和 3 与 4,贝茜会被卡住,如果她从(0,0)到(1,0)之间的任意位置开始或(0,1)和(1,1)之间。

| . . . .4 3 . . .      贝茜会穿过B,A,1-2-.-.-.      然后再次穿过B

相似的,在相同的起始点,如果配对是 1-3 和 2-4,贝茜也会陷入循环。(如果贝西从3进去,1出来,她会走向2,然后被传送到4,最后又回到3)

仅有1-4和2-3的配对允许贝茜从任何二维平面上的点向+x方向走不出现循环。

首先我的思路是这样的(暴力链接两个点):

for(int i=1;i<=n;++i){    for(int j=i+1;j<=n;++j){        if(!lk[i]&&!lk[j]){            lk[i]=j,lk[j]=i;            dfs(dep+1);            lk[i]=lk[j]=0;        }    }}

用两重循环去枚举

但ghj说这样太慢,容易超时

因为对于可以链接的点(lk[i]==0)我们只去枚举第一个点和后面那些点链接

而不用两重循环去枚举(这样会有重复状态)

其实就是一个小优化:

for(int i=1;i<=n;++i){    if(!lk[i]){        for(int j=i+1;j<=n;++j){            if(!lk[j]){                lk[i]=j,lk[j]=i;                dfs(dep+1);                lk[i]=lk[j]=0;            }        }        break;//划重点    }}

然后就是判环

ghj大佬说环有两种情况:

我们先按y为第一关键字,x为第二关键字排序,则x若有右边可以到达的点

则那个点的编号肯定为x+1

lk.png

这样就形成了一个环

但是还有另外一种情况:

lk.png

这样就不是一个环

所以在判环的时候要判断一下

#include
#include
#include
using namespace std;#define dou 0const int maxn=15;int n,m;struct p{ int x,y; friend bool operator < (const p &a,const p &b){return a.y==b.y? a.x

转载于:https://www.cnblogs.com/eric-walker/p/9614687.html

转载地址:https://blog.csdn.net/dengxingrao0615/article/details/102231342 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:线段树
下一篇:background

发表评论

最新留言

哈哈,博客排版真的漂亮呢~
[***.90.31.176]2024年03月27日 13时42分35秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

wget连接指定端口_端口通不通 telnet wget ssh 2019-04-21
eureka 调用服务_Spring Cloud微服务架构从入门到会用(二)—服务注册中心Eureka... 2019-04-21
easyexcel 工具类_问了个在阿里的同学,他们常用的15款开发者工具! 2019-04-21
mysql统计结果大于0时返回true_mysql表查询练习 2019-04-21
c语言对结构体排序中间变量,求助:c语言怎么实现结构体的排序? 总是弄不对啊... 2019-04-21
c语言宏定义只能在最前面吗,C语言宏定义注意事项 2019-04-21
android悬浮窗服务卡死,Android 悬浮窗兼容问题谈 2019-04-21
表格相关的html语言,HTML标记语言——表格标记 2019-04-21
web聊天界面html,PC端Web聊天界面+代码分享(HTML+CSS) 2019-04-21
cmake qt 添加路径 项目_CMake配置Qt工程 2019-04-21
使用python开发的软件协议_WEB开发——Python WSGI协议详解 2019-04-21
冰点下载器手机版apk_冰点文库下载器 2019-04-21
python信号采集代码_13行代码实现:Python实时视频采集(附源码) 2019-04-21
h5引入json_纯js直接引入json文件 2019-04-21
python格式化字符串总结_Python字符串处理方法总结 2019-04-21
python中true什么意思_python中的bool是什么意思 2019-04-21
jacobian 矩阵意义_Jacobian矩阵和Hessian矩阵的作用是什么? 2019-04-21
c++ jna 数据类型_JNA 使用总结 2019-04-21
python中如何遍历列表并将列表值赋予_python中如何实现遍历整个列表? 2019-04-21
apache php mysql架构图_Apache+PHP+MYSQL+Tomcat+JK架构设计技巧与应用实战 2019-04-21