【UOJ #210】【UER #6】寻找罪犯（2-sat 详解）

【UOJ #210】【UER #6】寻找罪犯

题目描述

通过一些不可描述的方式，妹滋滋算出了 51% 的得票率，于是就她就把这个公开给了广大用户 —— UOJ 解散已成定局。

几个小时后，UOJ 创始人伏特跳蚤国王宣布辞职，即日起退出 UOJ 团队。

这两个消息在算法竞赛界引起了轩然大波，“UOJ 是什么”“废除UOJ有什么影响” 马上成为了网民们的搜索热点并出现在了各大搜索网站的首页上。

著名的大水群和三连击发源地 —— Universal OJ 用户群随之解散，导致大量 OI 水狗们无处可水。一段时间后，圈子里渐渐传出了恢复 UOJ 的呼声，更有一些人将这个烂摊子归咎于那些投票通过的用户 —— 他们决定找出这些人并加以指责。

经过一段时间的搜索，他们找到了 n 个嫌疑人，编号为 1 到 n，导致 UOJ 解散的犯人就在他们之间。严刑拷打之下，他们交代了一些供词，供词有两类：

xi 说 yi 是犯人。

xi 说 yi 不是犯人。

然而，让事情变得复杂的是，犯人们并不打算背锅，所以他们的供词不总是真的，同时，为了不闹乌龙暴露自己，每一个犯人的所有供词最多有一句是假的，而不是犯人的嫌疑人的供词总是真的。

现在给出了全部的 m 条供词，你需要找出哪些人是犯人。如果有多解，输出任何一组解即可。

输入格式

第一行两个正整数 n,m，表示犯人数目与供词数目。

接下来 m 行，每行三个整数 xi,yi,ti。其中 ti=0 表示 xi 说 yi 是犯人，ti=1 表示 xi 说 yi 不是犯人。

输出格式

第一行一个整数 c 表示犯人的数目。

第二行 c 个整数 pi，按照升序输出所有犯人的编号。

如果不存在一个犯人的集合使得供词满足条件，输出一行一个单词 “Impossible”。

样例一

input

2 2

1 2 0

2 1 0

output

1 2

explanation

容易看出除了没有犯人的情况，其他三种情况都是满足条件的。

样例二

input

3 4

1 1 1

2 2 1

1 3 1

2 3 0

output

Impossible

explanation

不论如何，第 3,43,4 条证言都一定是真的，而这两条证言互相矛盾。

思路：

2-SAT。

抽象的理解一下就是说，把你的推理思路建成边，如果你可以从A条件推得B条件，那么就可以建立一条从A到B的有向边。

针对这道题，我们需要推理出的是每个人的真假（是不是罪犯），以及每句话的真假。

考虑将一个人拆成两个点，表示他是犯人和他不是犯人。

若他不是犯人，那么他说的话都是真的，那么就可以通过他的供词推出他说的人是不是犯人。（也就是从他不是犯人的点连向他供词的结论，以及他所有话是真话的点）

如果有人说他是犯人，那么可以推出他肯定是犯人。（也就是从他不是犯人的点连向指认他的人是犯人的点）

若他是犯人，那么可以推出所有说他不是犯人的人一定是犯人。（也就是从他是犯人的点连向保护他的人是犯人的点）

因为他只能说一句谎话，所有他说的话的反命题一定可以推出他的其他话一定是对的。（也就是从他说的假话的点连向他说的其他话是真话的点）

然而这样的话边数太多，是会炸掉的，所以考虑用前/后缀和优化构图。

就是说我们的真话点表示的是这个人说的这句话及他之前说的话都是真话，假话点表示的是这个人说的这句话及他之前说的话中有一句假话。

所以说我们的推导条件变成了：

如果此人之前的话中有假话，那么这句话一定是真话。（也就是前一句话的假话点连向后一句话的真话点）

如果此人这句话及以前的话都是真话，则此人之前的话也是真话（也就是真话点连向之前的真话点）。

如果此人以前的话中有假话，那么如果此人这句话及以前的话中也有假话（也就是假话点连向之后的假话点）。

这样就大大减少了边的数量（可以自己画个图感受一下）

然后就是F11了。

关于如何判无解与输出方案：

把可以推出的关系看做有向图的边，那么一个强连通分量就可以看做等价的命题。如果两个矛盾的命题是等价的，（即一个人既是犯人又不是犯人）那么就无解。

输出方案时，考虑强连通分量中的每一个点的反命题，如果反命题选了，那么这一整个强连通分量就不能选了，不然就可以选。所以我们可以先遇到就选择，之后遇到了反命题就跳过。

当然，这道题还有其他的构图方式，只要把所有矛盾的情况带入图中看看是否都可以辨认出就行。

#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;

const int maxn = +;
int n, m, o, idc, top, tot, idx, cnt;
int head[maxn], dfn[maxn], low[maxn], scc[maxn], st[maxn], np[maxn], print[maxn];
struct Edge { int next, to; } ed[maxn<<];

void adde(int u, int v) {
    ed[++idc] = (Edge){ head[u], v }; head[u] = idc;
    ed[++idc] = (Edge){ head[v^], u^ }; head[v^] = idc;
}

void tarjan(int x) {//判强连通分量
    dfn[x] = low[x] = ++idx;
    st[++top] = x;
    for(int k=head[x]; k; k=ed[k].next) {
        int v = ed[k].to;
        if(!dfn[v]) tarjan(v), low[x] = min(low[x], low[v]);
        else if(!scc[v]) low[x] = min(low[x], dfn[v]);
    }
    if(low[x] == dfn[x]) {
        ++tot;
        while(top) {
            int v = st[top--];
            scc[v] = tot;
            if(v == x) break;
        }
    }
}

int id(int x, int d) { return x<<|d; }//代表身份的点2~2n+1，奇数是罪犯，偶数不是 
int say(int x, int d) { return (n+x)<<|d; }//代表供词的点2n+4~2n+2m+2，奇数是真话，偶数不是 

int main() {
    scanf("%d%d", &n, &m);
    o = say(m+, )+;//总点数 
    for(int i=; i<=n; ++i) np[i] = ;
    for(int i=; i<=m+; ++i) {
        int x, y, t;
        scanf("%d%d%d", &x, &y, &t), t = !t;
        adde(id(y, !t), say(np[x], ));//这句话是假的，那么此人之前的话中没有假话 
                                       //如果此人之前的话中有假话，那么这句话一定是真话 
        adde(say(i, ), id(y, t));//此话为真对应一个身份，已知身份就能辨别话的真假 
        adde(say(i, ), say(np[x], ));//如果此人这句话及以前的话都是真话，则此人之前的话也是真话
                                       //如果此人以前的话中有假话，那么如果此人这句话及以前的话中也有假话
        np[x] = i;//更新这个人上一个供词的pos 
    }
    for(int i=; i<=n; ++i) adde(say(np[i], ), id(i, ));//说假话的是罪犯 
    for(int i=o; i; --i) if(!dfn[i]) tarjan(i);
    for(int i=; i<=o; i+=) 
        if(scc[i] == scc[i^]) return puts("Impossible"), ;//从false 推到了true
    for(int i=; i<=n; ++i)
        if(scc[id(i, )] < scc[id(i, )]) print[++cnt] = i;//命题跟逆命题之间统一选择先出现的一个 
    printf("%d\n", cnt);
    for(int i=; i<=cnt; ++i) 
        printf("%d%c", print[i], i == cnt ? '\n' : ' ');
    return ;
}

【UOJ #210】【UER #6】寻找罪犯（2-sat 详解）