BZOJ_2199
这个题目可以枚举每个方案是Y还是N，然后用2-SAT判断是否可以the bills are to be passed or not in such a way that every cow gets her way on at least one of her votes，整体复杂度是O(N*M)的。
#include<stdio.h> #include<string.h> #include<algorithm> #define MAXN 2010 #define MAXM 8010 int N, M, one[MAXM], two[MAXM], first[MAXN], e, next[MAXM], v[MAXM]; int ins[MAXN], s[MAXN], color[MAXN], dfn[MAXN], low[MAXN], cnt, top, col; void init() { int x; char b[5]; N *= 2; for(int i = 0; i < M; i ++) { scanf("%d%s", &x, b); if(b[0] == 'Y') one[i] = 2 * (x - 1) + 1; else one[i] = 2 * (x - 1); scanf("%d%s", &x, b); if(b[0] == 'Y') two[i] = 2 * (x - 1) + 1; else two[i] = 2 * (x - 1); } } void add(int x, int y) { v[e] = y; next[e] = first[x], first[x] = e ++; } void build() { for(int i = 0; i < M; i ++) add(one[i] ^ 1, two[i]), add(two[i] ^ 1, one[i]); } void tarjan(int x) { dfn[x] = low[x] = ++ cnt; s[top ++] = x, ins[x] = 1; for(int i = first[x]; i != -1; i = next[i]) { if(dfn[v[i]] == 0) { tarjan(v[i]); low[x] = std::min(low[x], low[v[i]]); } else if(ins[v[i]] && dfn[v[i]] < low[x]) low[x] = dfn[v[i]]; } if(low[x] == dfn[x]) { ++ col; for(s[top] = -1; s[top] != x;) color[s[--top]] = col, ins[s[top]] = 0; } } int judge() { top = cnt = col = 0; memset(dfn, 0, sizeof(dfn[0]) * (N + 1)); memset(ins, 0, sizeof(ins[0]) * (N + 1)); for(int i = 0; i < N; i ++) if(!dfn[i]) tarjan(i); for(int i = 0; i < N; i += 2) if(color[i] == color[i ^ 1]) return 0; return 1; } int report[MAXN]; void solve() { for(int i = 0; i < N; i += 2) { int flag = 0; report[i / 2] = 0; memset(first, -1, sizeof(first[0]) * (N + 1)), e = 0; add(i, i ^ 1), build(); if(judge()) ++ report[i / 2], flag = 1; memset(first, -1, sizeof(first[0]) * (N + 1)), e = 0; add(i ^ 1, i), build(); if(judge()) -- report[i / 2], flag = 1; if(flag == 0) { printf("IMPOSSIBLE\n"); return ; } } for(int i = 0; i < N; i += 2) { if(report[i / 2] == -1) putchar('N'); else if(report[i / 2] == 0) putchar('?'); else putchar('Y'); } putchar('\n'); } int main() { while(scanf("%d%d", &N, &M) == 2) { init(); solve(); } return 0; }