题目链接: The Continental Cowngress G

简述 :
给出 $n$ 个法案， $m$ 头牛的意见， 每头牛会表决两次。
每次表决格式为 i Y 表示“支持 $i$ 号法案”或 i N 表示“反对 $i$ 号法案”。
最终，每头牛至少要有一个表决被满足。不可能成立的话输出 IMPOSSIBLE，否则输出方案。

由于对 Farmer John 的领导感到极其不悦，奶牛们退出了农场，组建了奶牛议会。

议会以“每头牛都可以获得自己想要的”为原则，建立了下面的投票系统： $M$只到场的奶牛 ( $1\le M\le 4000$ ) 会给 $N$ 个议案投票 ( $1\le N\le 1,000$ ) 。每只奶牛会对恰好两个议案 $B_i$ 与 $C_i$ ( $1\le B_i \le N$ ; $1 \le C_i \le N$ ) 投出“是”或“否”（输入文件中的 Y 和 N ）。

他们的投票结果分别为 $V_{B_i}$ ( $V_{B_i} \in { \texttt{Y}, \texttt{N}})$ 与 $V_{C_i} (V_{C_i} \in {\texttt{Y}, \texttt{N}})$。 最后，法案会以如下的方式决定：每只奶牛投出的两票中至少有一票和最终结果相符合。 例如 Bessie 给法案 $1$ 投了赞成 Y，给法案 $2$ 投了反对 N，那么在任何合法的法案通过方案中，必须满足法案 $1$ 必须是 Y或者议案 $2$ 必须是 N（或者同时满足）。

你的工作是确定哪些法案可以通过，哪些不能。

如果不存在这样一个方案， 输出 IMPOSSIBLE。

如果至少有一个解，对于每个法案输出：

  • Y 如果在每个解中，这个法案都必须通过。
  • N 如果在每个解中，这个法案都必须驳回。
  • ? 如果有的解这个法案可以通过，有的解中这个法案会被驳回。

思路 : 每头牛都有两个表决且至少有一个表决被同意, 满足二分图, 建立2-sat模型. 然后对于每个表决的两种情况都dfs一遍, 若x与!x都存在, 那么就说明无解.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
//#pragma GCC optimize(2)
//#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace::std;
#define fi first
#define se second
#define lc (x << 1)
#define rc (x << 1 | 1)
#define mid ((l + r) >> 1)
#define zty(x) cout << #x << " = " << x << '\n';
const int MAX_N = 2005;
const int MAX_M = 2e5 + 5;
const int mod = 998244353;
const int INF = 0x3f3f3f3f;

int n, m;
int head[MAX_N], tot;
struct node { int to, next;} G[MAX_M];
inline void add(int u, int v) {
    G[++ tot] = node{v, head[u]};
    head[u] = tot;
}
int dfn[MAX_N], low[MAX_N], col[MAX_N], cnt, num;
stack< int > st;
bool vis[MAX_N];
void tarjan(int x) {
    dfn[x] = low[x] = ++ num;
    st.push(x);
    for(int i = head[x]; i; i = G[i].next) {
        int y = G[i].to;
        if(!dfn[y]) {
            tarjan(y);
            low[x] = min(low[x], low[y]);
        } else if(!col[y]) {
            low[x] = min(low[x], dfn[y]);
        }
    }
    if(dfn[x] == low[x]) {
        col[x] = ++ cnt;
        while(st.top() != x) {
            col[st.top()] = cnt;
            st.pop();
        }
        st.pop();
    }
}
void dfs(int x) {
    vis[x] = true;
    for(int i = head[x]; i; i = G[i].next) {
        int y = G[i].to;
        if(!vis[y]) dfs(y);
    }
}
bool check(int x) {
    memset(vis, 0, sizeof(vis));
    dfs(x);
    for(int i = 1; i <= n; ++ i) {
        if(vis[i] && vis[i + n]) return false;
    }
    return true;
}
void solve() {
    cin >> n >> m;
    // i means support and i + n means reject.....
    while(m -- ) {
        int a, b;
        string op1, op2;
        cin >> a >> op1 >> b >> op2;
        if(op1 == "Y") {
            if(op2 == "Y") {
                add(b + n, a); add(a + n, b);
            } else {
                add(b, a); add(a + n, b + n);
            }
        } else {
            if(op2 == "Y") {
                add(b + n, a + n); add(a, b);
            } else {
                add(b, a + n); add(a, b + n);
            }
        }
    }
    for(int i = 1; i <= n * 2; ++ i) {
        if(!dfn[i]) tarjan(i);
    }
    for(int i = 1; i <= n; ++ i) {
        if(col[i] == col[i + n]) {
            cout << "IMPOSSIBLE" << '\n';
            return;
        }
    }
    string ret;
    for(int i = 1; i <= n; ++ i) {
        bool f1 = check(i), f2 = check(i + n);
        if(f1 && f2) ret += "?";
        if(f1 && !f2) ret += "Y";
        if(!f1 && f2) ret += "N";
    }
    cout << ret << '\n';
}
signed main() {
//    freopen("SPO.IN", "r", stdin);
//    freopen("SPO.OUT", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int ZTY = 1;
    //cin >> ZTY;
    while(ZTY -- ) solve();
    return 0;
}