http://acm.hdu.edu.cn/showproblem.php?pid=2828
给定n个灯，m个开关，使得每栈灯亮，前提是控制这栈灯的开关的状态是其中一个。（题目应该都看得懂）
其实我想了挺久的，比赛的时候还想不出。但是直觉就告诉我是二分图匹配，虽然网上说什么精确覆盖。
不懂。
我的做法是：
m个开关，则有2 * m种状态，以1号顶点表示1号灯是开得，1 + m号顶点表示1号灯是关的。
那么，进行一次二分匹配，模板需要改一下，
1、如果第i号灯需要第j个开关是ON的状态，但是第j个开关的ON的状态已经被人选了，那么，就可以默认第i号灯是true的了。
2、如果你想选第j个开关是OFF的状态，那么就要询问下第j个开关的ON的状态是否被别人选了，如果是，就进行套路，就是找增广路。
3、记得修改match[i]，这里卡了我wa，不知道怎么说，看看代码吧。
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <bitset>
int n, m;
const int maxn = * ;
struct Edge {
int u, v, tonext;
}e[maxn * ];
int num, first[maxn];
void add(int u, int v) {
++num;
e[num].u = u, e[num].v = v, e[num].tonext = first[u];
first[u] = num;
}
bool book[maxn * ];
int match[maxn * ];
bool dfs(int u) {
for (int i = first[u]; i; i = e[i].tonext) {
int v = e[i].v;
if (book[v] == false) {
book[v] = true;
if (v > m) book[v - m] = true;
else book[v + m] = true;
if (match[v]) return true;
if (v > m) {
if (match[v - m] == || dfs(match[v - m])) {
match[v - m] = ;
match[v] = u;
return true;
}
} else {
if (match[v + m] == || dfs(match[v + m])) {
match[v + m] = ; //dfs那里的要清空
match[v] = u;
return true;
}
}
}
}
return false;
}
int hungary() {
int ans = ;
for (int i = ; i <= n; ++i) {
memset(book, false, sizeof book);
if (dfs(i)) ans++;
}
return ans;
}
void init() {
memset(first, , sizeof first);
memset(match, , sizeof match);
num = ;
}
void work() {
init();
for (int i = ; i <= n; ++i) {
int k;
scanf("%d", &k);
while (k--) {
int id;
char op[];
scanf("%d%s", &id, op);
if (op[] == 'N') {
add(i, id);
} else {
add(i, id + m);
}
}
}
int res = hungary();
if (res != n) {
cout << "-1" << endl;
return;
}
// for (int i = 1; i <= n; ++i) {
// cout << match[i] << " ";
// }
// cout << endl;
for (int i = ; i <= m - ; ++i) {
if (match[i]) {
printf("ON ");
} else {
printf("OFF ");
}
}
if (match[m]) {
printf("ON");
} else printf("OFF");
printf("\n");
} int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
while (scanf("%d%d", &n, &m) != EOF) work();
return ;
}