首页 > 代码库 > Codeforces 776D：The Door Problem（DFS染色）
Codeforces 776D：The Door Problem（DFS染色）
http://codeforces.com/problemset/problem/776/D
题意：有n个门，m个开关，每个门有一个当前的状态（0表示关闭，1表示打开），每个开关控制k个门，但是每个门确切的受两个开关控制，如果一个开关打开，那么原来关闭的门会打开，打开的门关闭，问是否存在一个情况使得所有的门打开。
思路：类似于01染色，把开关当成点，门当前的状态当成边权建图。初始先假设一个门的状态（初始假设为0和假设为1都是一样的，举几个例子就发现了），然后因为每个门受两个开关控制，所以可以推出下一个门的状态，如果发现互斥的情况，那么就是“NO”。
这里设成门状态0表示打开，1表示关闭，方便运算。
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define N 200010 4 struct Edge { 5 int v, nxt, w; 6 } edge[N*2]; 7 int col[N], fir[N], sec[N], head[N], tot, w[N]; 8 9 void Add(int u, int v, int w) {10 edge[tot] = (Edge) {v, head[u], w}; head[u] = tot++;11 edge[tot] = (Edge) {u, head[v], w}; head[v] = tot++;12 }13 14 bool dfs(int u) {15 for(int i = head[u]; ~i; i = edge[i].nxt) {16 int v = edge[i].v, w = edge[i].w;17 if(col[v] == -1) { // 如果这个开关没染色18 col[v] = col[u] ^ w;19 if(!dfs(v)) return false;20 } else if(col[u] ^ col[v] ^ w) return false; // 如果染过色并发生矛盾21 }22 return true;23 }24 25 int main() {26 int n, m;27 cin >> n >> m;28 for(int i = 1; i <= n; i++) scanf("%d", &w[i]), w[i] ^= 1;29 for(int i = 1; i <= m; i++) {30 int k; scanf("%d", &k);31 while(k--) {32 int a; scanf("%d", &a);33 if(fir[a] == 0) fir[a] = i; // 连a点的第一个开关34 else sec[a] = i; // 连a点的第二个开关35 }36 }37 memset(head, -1, sizeof(head)); tot = 0;38 for(int i = 1; i <= n; i++)39 Add(fir[i], sec[i], w[i]);40 memset(col, -1, sizeof(col));41 bool flag = 1;42 for(int i = 1; i <= m; i++) {43 if(col[i] == -1) {44 col[i] = 0; // 假设这个开关一开始是关的45 if(!dfs(i)) { flag = 0; break; }46 }47 }48 if(!flag) puts("NO");49 else puts("YES");50 return 0;51 }
Codeforces 776D：The Door Problem（DFS染色）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。