一家旅馆的 n 间不同的房间里困住了 n 个人，其中有些房间是被锁住了，有些房间是打开的，但是只有在所有房间同时打开的情况下，被困人员才能逃离。现在有 m 个开关，每个开关控制着一些房间的门，开关的作用是使得这些房间原来开着的关上，关上的打开，但每个门都被两个开关控制。
【输入格式】
第一行，有两个正整数 n 和 m（2 ≤ n, m ≤ 10^5） ， n 表示房间的数量，m 表示开关的数量。 第二行 n 个数，表示每个房间的状态，0 表示房间是锁住的，1 表示房间是开着的。
再接下来 m 行，每行第一个数 x 表示第 i 把锁控制的房间数，再接着有 x 个数，分别表示所控制的房间编号（1~n） 。
数据保证每个房间是被两个开关控制的。
【输出格式】
如果房间都能被打开则输出“YES”，否则输出“NO”
输入样例#1：
3 3
1 0 1
2 1 3
2 1 2
2 2 3
输出样例#1：
NO
输入样例#2：
3 3
1 0 1
3 1 2 3
1 2
2 1 3
输出样例#2：
YES
输入样例#3：
3 3
1 0 1
3 1 2 3
2 1 2
1 3
输出样例#3：
NO
由于每个门只会被两个钥匙控制，那么两个钥匙的选或不选就能建立起一种对应关系。即如果门本来是开着的，那么用了一把必须用另一把，不用一把必须不用另一把；如果们本来是开着的，那么不用一把必须用另一把，用了一把必须不用另一把。
#include <bits/stdc++.h> using namespace std; const int maxn = 5e5 + 5; int low[maxn], dfn[maxn]; int head[maxn], tot, scc[maxn]; int n, m, Index, ins[maxn], cnt; int a[maxn]; stack<int> st; struct Edge { int u, v, next; }edge[maxn << 1]; vector<int> vec[maxn]; void init() { memset(head, -1, sizeof(head)); tot = 1; } void add(int u, int v) { edge[++tot].u = u; edge[tot].v = v; edge[tot].next = head[u]; head[u] = tot; } void tarjan(int u) { low[u] = dfn[u] = ++Index; ins[u] = 1; st.push(u); for (int i = head[u]; i != -1; i = edge[i].next) { int to = edge[i].v; if (!dfn[to]) { tarjan(to); low[u] = min(low[u], low[to]); } else if (ins[to]) { low[u] = min(low[u], dfn[to]); } } if (low[u] == dfn[u]) { ++cnt; int v; do { v = st.top(); ins[v] = 0; st.pop(); scc[v] = cnt; } while (v != u); } } int sat() { for (int i = 1; i <= m; i++) { if (scc[i] == scc[i + m]) { return false; } } return true; } int main() { init(); int x, y; cin >> n >> m; for (int i = 1; i <= n; i++) { cin >> a[i]; } for (int i = 1; i <= m; i++) { cin >> y; for (int j = 1; j <= y; j++) { cin >> x; vec[x].push_back(i); } } for (int i = 1; i <= n; i++) { int u = vec[i][0], v = vec[i][1]; if (a[i]) { //如果门本来是开着的，则选择了一把，就必须选择另外一把 add(u, v); add(v, u); add(u + m, v + m); add(v + m, u + m); } else { //如果门本来是关着的，着选择了一把，就不能选择另外一把 add(u, v + m); add(v + m, u); add(u + m, v); add(v, u + m); } } for (int i = 1; i <= 2 * m; i++) { if (!dfn[i]) { tarjan(i); } } if (sat()) { cout << "Yes" << endl; } else { cout << "No" << endl; } return 0; }
![洛谷P2639-[USACO09OCT]Bessie‘s Weight Problem G（01背包）](https://ucc.alicdn.com/images/user-upload-01/20200726093842419.png?x-oss-process=image/resize,h_160,m_lfit)