【codeforces 776D】The Door Problem
The Codeforces Problem
2023-09-14 09:03:48 时间
【题目链接】:http://codeforces.com/contest/776/problem/D
【题意】
每个门严格由两个开关控制;
按一下开关,这个开关所控制的门都会改变状态;
问你能不能使所有的门都打开(同时);
【题解】
/*
对于每个门,
有两个开关连接着它;
用一条边连接这两个开关
则如果这个门的状态是关的,
则这条边的边权为1
表示它们俩的颜色不能一样;
(也即这两个开关只能改变一个)
也即要1开1关;
如果这个门的状态是开的
则这条边的边权为0;
表示它们俩的颜色相同;
即同时开或同时关.
然后做一个二分图染色
可以就是YES否则NO
也就是说把开关看成节点,门看成边,根据边来确定这条边的两端的节点的颜色是一样还是不同;
*/
【完整代码】
#include <iostream>
#include <vector>
#include <cstdio>
#include <cstdlib>
#define rei(x) cin >> x
#define rep1(i,x,y) for (int i = x;i <= y;i++)
using namespace std;
const int N = 2e5 + 100;
int n, m, a[N],color[N];
vector <int> g1[N],g[N],w[N];
void dfs(int x, int c)
{
color[x] = c;
int len = g[x].size();
rep1(i, 0, len - 1)
{
int y = g[x][i];
int ju = w[x][i];
if (color[y] != 0)
{
if (ju == 1 && color[y] == color[x])
{
puts("NO");
exit(0);
}
if (ju == 0 && color[y] != color[x])
{
puts("NO");
exit(0);
}
}
else
if (ju == 0)
dfs(y, c);
else
dfs(y, 3 - c);
}
}
int main()
{
//freopen("D:\\rush.txt", "r", stdin);
rei(n),rei(m);
rep1(i, 1, n)
rei(a[i]);
rep1(i, 1, m)
{
int num;
rei(num);
rep1(j, 1, num)
{
int x;
cin >> x;
g1[x].push_back(n + i);
g1[n + i].push_back(x);
}
}
rep1(i, 1, n)
{
int y1 = g1[i][0], y2 = g1[i][1];
int bian = 1 - a[i];
g[y1].push_back(y2), g[y2].push_back(y1);
w[y1].push_back(bian),w[y2].push_back(bian);
}
rep1(i,n+1,n+m)
if (color[i] == 0)
dfs(i, 1);
puts("YES");
return 0;
}
相关文章
- SP Module 9 the Hidden Markov Model
- 【错误记录】Android 编译报错 ( The minCompileSdk (31) specified in a dependency‘s AAR metadata (META-INF/com )
- The unit caddy.service has entered the 'failed' state with result 'exit-code'
- ORA-21602: operation does not support the specified typecode ORACLE 报错 故障修复 远程处理
- ORA-22955: The cardinality parameter is not within the allowed limits ORACLE 报错 故障修复 远程处理
- ORA-27611: Smart I/O failed due to a block corruption detected on the host. The block was received from cell “string”. disk: “string”, block: “string”, disk offset: “string” ORACLE 报错 故障修复 远程处理
- ORA-02829: No segment of the proper size is available ORACLE 报错 故障修复 远程处理
- ORA-32411: materialized view definition query exceeds the maximum length ORACLE 报错 故障修复 远程处理
- ORA-48140: the specified ADR Base directory does not exist [string] ORACLE 报错 故障修复 远程处理
- ORA-48442: The control parameter number exceeds the maximum number [string] ORACLE 报错 故障修复 远程处理
- ORA-48485: The file exceeds the maximum length [string] ORACLE 报错 故障修复 远程处理
- ORA-55640: Insufficient privilege to perform the Flashback Data Archive operation ORACLE 报错 故障修复 远程处理
- ORA-01378: The logical block size (string) of file string is not compatible with the disk sector size (media sector size is string and host sector size is string) ORACLE 报错 故障修复 远程处理
- ORA-06514: PL/SQL: The remote call cannot be handled by the server ORACLE 报错 故障修复 远程处理
- ORA-07672: $PARSE_CLASS failed translating the string into a binary label ORACLE 报错 故障修复 远程处理
- ORA-09914: Unable to open the ORACLE password file. ORACLE 报错 故障修复 远程处理
- ORA-13227: SDO_LEVEL values for the two index tables do not match ORACLE 报错 故障修复 远程处理
- ORA-13859: Action cannot be specified without the module specification ORACLE 报错 故障修复 远程处理
- Linux Ape: Unleashing the Power of OpenSource Solutions(linuxape)
- MySQL: Exploring the Maximal Record Limit(mysql最大记录)
- Exploring the Power of MongoDB: The Definitive Guide to Upgrading Arrays(mongodb更新数组)
- Exploring the World of Image Viewing on Linux(linux看图片)
- Discover the Power of Photon Linux: A Comprehensive Guide to the Lightweight Operating System(photonlinux)
- Unveiling the Evolution of Linux: The Journey of the 0.11 Version(linux0.11)
- Oracle介绍The函数的应用(oracle the函数)
- 优化技巧 (Note The title provided by the AI is incomplete Heres a suggestion for a title that completes the phrase)