P3007

FiraCode · 2022-11-04 19:31:40 · 题解

题目链接

我们要判断一个变量恒为真/假/真假都可以。

方法一

我们可以强行设 x_i 为假，若无解，那么 x_i 一定为真或真假都行，或都不行。

要跑 n 次，所以时间复杂度是 O(nm)。

方法二

若 x_i 是指向 \neg x_i 的话，我们就一定选 x_i 为假。

若 \neg x_i 是指向 x_i 的话，我们就一定选 \neg x_i 为假。

否则若 \neg x_i 和 x_i 没有可达关系，那么就是 ?。

那么这样的话，我们就可以判断两个点是否有可达关系就可以了，而判断可达关系的话就可以用 BFS 或 DFS。

时间复杂度为 O(n^2)。

CODE:

#include <bits/stdc++.h>
using namespace std;
const int N = 2010;
int n, m;
bool ins[N], vis[N];
vector<int> e[N];
int dfn[N], low[N], idx, bel[N];
stack<int> stk;
int cnt;
char ans[N];
void taryan(int u) {//联通分量
    dfn[u] = low[u] = ++idx;
    ins[u] = true;
    stk.push(u);
    for (auto v: e[u]) {
        if (!dfn[v]) taryan(v);
        if (ins[v]) low[u] = min(low[u], low[v]);
    }
    if (dfn[u] == low[u]) {
        ++cnt;
        while (true) {
            int v = stk.top();
            bel[v] = cnt;
            ins[v] = false;
            stk.pop();
            if (u == v) break;
        }
    }
}
void dfs2(int u) {//dfs
    vis[u] = 1;
    for (auto v : e[u]) if (!vis[v])
        dfs2(v);
}
bool check(int s, int t) {
    memset(vis, false, sizeof(vis));
    dfs2(s);
    return vis[t];
}
int main() {
    scanf("%d%d", &n, &m);
        for (int i = 1; i <= m; ++i) {
        int u, v;
        char ty1[2], ty2[2];
        scanf("%d%s%d%s", &u, ty1, &v, ty2);
        --u, --v;
        u = (u * 2) + (*ty1 == 'Y');
        v = (v * 2) + (*ty2 == 'Y');
        e[u ^ 1].push_back(v);
        e[v ^ 1].push_back(u);
    }
    for (int i = 0; i < 2 * n; ++i) if (!dfn[i])
        taryan(i);
    for (int i = 0; i < n; ++i) {
        if (bel[i << 1] == bel[i << 1 | 1]) {
            puts("IMPOSSIBLE");//无解
            return 0;
        }
    }
    for (int i = 0; i < n; ++i) {
        if (check(2 * i, 2 * i + 1)) ans[i] = 'Y';//当i*2是2*i+1,则第i个恒为真
        else if (check(2 * i + 1, 2 * i)) ans[i] = 'N';//另一种情况
        else ans[i] = '?';//因为不会是无解，所以就是?
    }
    puts(ans);
    return 0;
}