并查集+思维——The Door Problem
2024-09-30 06:56:09
一、问题描述(题目链接)
有n个门和m个开关,每个开关可以控制任意多的门,每个门严格的只有两个开关控制,问能否通过操作某些开关使得所有门都打开。(给出门的初始状态)。
二、问题分析
大部分开关问题首先要想到的一点就是任何开关操作两次以上都是无意义的,因此对于每个开关,我们要么操作一次,要么不操作。
因为已知门的初始状态,每个门由两个开关控制,所以我们可以调节这两个开关,使门保持打开的状态。
我们考虑用并查集维护开关之间的关系,因为每个开关有操作和不操作两种状态。,因此,我们要把每个点拆成两个点,i表示第i个开关没操作过,i+m表示第i个开关操作过。
若第i个门初始状态为1,控制开关为a和b,则合并a,b和a+m,b+m。
若初始状态为0,则合并a,b+m和b,a+m
最后判断i 和i+ m是否在同一集合,有任意一个,则不存在使门全部呈打开状态的操作。
三、代码实现
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std; const int maxn = + ;
const int maxm = + ;
int n, m, sta[maxn];
int fa[ * maxn];
vector<int>door[maxn]; void init()
{
for (int i = ; i <= * maxm; i++)
fa[i] = i;
} int findset(int x)
{
if (x != fa[x])
return fa[x] = findset(fa[x]);
return fa[x];
} void unite(int x, int y)
{
int rx = findset(x);
int ry = findset(y);
fa[rx] = ry;
} int main()
{
int flag = ;
init();
scanf("%d%d", &n, &m);
for (int i = ; i <= n; i++)
scanf("%d", &sta[i]);
for (int i = ; i <= m; i++)
{
int cnt,tmp;
scanf("%d", &cnt);
while (cnt--)
{
scanf("%d", &tmp);
door[tmp].push_back(i); //输入的是每个开关控制的门,我们要建立的是每个门由哪些开关控制
}
} for (int i = ; i <= n; i++)
{
if (sta[i])
{
unite(door[i][], door[i][]);
unite(door[i][] + m, door[i][] + m);
}
else
{
unite(door[i][] + m, door[i][]);
unite(door[i][], door[i][] + m);
}
}
for (int i = ; i <= m; i++)
{
if (findset(i) == findset(i + m))
{
flag = ;
break;
}
}
printf("%s\n", flag ? "YES" : "NO");
return ;
}
最新文章
- python网络编程-TCP协议中的三次握手和四次挥手(图解)
- ios常见的页面传值方式
- [No00001B]到底如何培养语感?
- linux基础-第十二单元 硬盘分区、格式化及文件系统的管理一
- URAL 1303. Minimal Coverage(DP)
- [Ubuntu] Profile error when launching google-chrome
- sprint 1 总结
- oracle触发器类型
- ubuntu下 apt-get install 下载的文件存放的目录
- Kmplayer播放器 绿色免安装版 2016 中文版
- Akka(10): 分布式运算:集群-Cluster
- 1.使用C++封装一个链表类LinkList
- PHAR系列之导言
- WordCount(java)
- [UE4]让箭头保持水平的第二种方法:Combinrotators、Delta(Rotator)
- centos7 安装freetype
- mysql57 centos7 使用
- 自学Zabbix2.4-web页面配置zabbix
- Microsoft JET Database Engine 错误 &#39;80004005&#39; 未指定错误
- linux权限管理之进程掩码