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

题目描述

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

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

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

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

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

xi 说 yi 是犯人。

xi 说 yi 不是犯人。

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

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

输入格式

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

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

输出格式

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

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

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

题解

2-SAT。

将一个人拆成两个点，表示他是犯人和他不是犯人。若他不是犯人，那么他说的话都是对的，那么就可以通过他是犯人推出他说的人是不是犯人。如果有人说他是犯人，那么可以推出他肯定是犯人。若他是犯人，那么可以推出所有说他不是犯人的人一定是犯人。因为他只能说一句谎话，所有他说的话的反命题一定可以推出他的其他话一定是对的。然而这样的话边数是m^2的，所以用前/后缀和优化构图即可。

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

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

输出方案时，考虑强连通分量中的每一个点的反命题，如果反命题选了，那么这一整个强连通分量就不能选了，不然就可以选。

代码

 #include <cstdio>

 #include <algorithm>

 #define R register

 #define maxn 400010

 #define cmin(_a, _b) (_a > (_b) ? _a = (_b) : 0)

 inline int F()

 {

     R char ch; R int cnt = ;

     while (ch = getchar(), ch < '' || ch > '') ;

     cnt = ch - '';

     while (ch = getchar(), ch >= '' && ch <= '') cnt = cnt *  + ch - '';

     return cnt;

 }

 struct Edge {

     Edge *next;

     int to;

 } *last[maxn << ], e[maxn << ], *ecnt = e;

 struct edge {

     edge *next; int to, w;

 } *lt[maxn], le[maxn << ], *lecnt = le, *rt[maxn], re[maxn << ], *recnt = re;

 inline void link1(R int a, R int b, R int w)

 {

     *++lecnt = (edge) {lt[a], b, w}; lt[a] = lecnt;

     *++recnt = (edge) {rt[b], a, w}; rt[b] = recnt;

 }

 inline void link(R int a, R int b)

 {

 //    printf("%d %d\n", a, b);

     *++ecnt = (Edge) {last[a], b}; last[a] = ecnt;

 }

 int dfn[maxn], low[maxn], timer, st[maxn], top, id[maxn], colcnt, n;

 bool fail, used[maxn];

 void tarjan(R int x, R int fa)

 {

     dfn[x] = low[x] = ++timer; st[++top] = x;

     for (R Edge *iter = last[x]; iter; iter = iter -> next)

         if (iter -> to != fa)

         {

             if (!dfn[iter -> to])

             {

                 tarjan(iter -> to, x);

                 cmin(low[x], low[iter -> to]);

             }

             else if (!id[iter -> to]) cmin(low[x], dfn[iter -> to]);

         }

     if (dfn[x] == low[x])

     {

         ++colcnt; R bool flag = ;

         for (; ;)

         {

             R int now = st[top--];

             id[now] = colcnt;

 //            printf("now %d colcnt %d\n", now, colcnt);

             if (now <=  * n)

             {

                 flag &= !used[id[now <= n ? now + n : now - n]];

                 now <= n ? fail |= (id[now + n] == id[now]) : fail |= (id[now - n] == id[now]);

             }

             if (now == x) break;

         }

         used[colcnt] = flag;

     }

 }

 int ans[maxn], tot;

 int main()

 {

     n = F(); R int m = F();

     for (R int i = ; i <= m; ++i)

     {

         R int a = F(), b = F(), w = F();

         link1(a, b, w);

     }

     R int ptot =  * n;

     for (R int i = ; i <= n; ++i)

     {

 //        printf("i = %d\n", i);

         R int lp = ptot, rp;

         for (R edge *iter = lt[i]; iter; iter = iter -> next)

         {

             link(i + n, iter -> to + n * iter -> w);

             ptot != lp ? link(ptot + , ptot),  : ;

             link(++ptot, iter -> to + n * iter -> w);

         }

         rp = ptot;

         for (R edge *iter = lt[i]; iter; iter = iter -> next)

         {

             if (iter != lt[i]) link(ptot, ptot + );

             link(++ptot, iter -> to + n * iter -> w);

         }

         for (R edge *iter = rt[i]; iter; iter = iter -> next)

             if (!iter -> w) link(i + n, iter -> to);

         R int counter = ;

         for (R edge *iter = lt[i]; iter; iter = iter -> next)

         {

             ++counter;

             if (iter != lt[i]) link(iter -> to + n * (iter -> w ^ ), lp + counter - );

             if (iter -> next) link(iter -> to + n * (iter -> w ^ ), rp + counter + );

 //            for (R edge *iter2 = lt[i]; iter2; iter2 = iter2 -> next)

 //                if (!(iter -> to == iter2 -> to && iter -> w == iter2 -> w))

 //                {

 //                    link(iter -> to + n * (iter -> w ^ 1), iter2 -> to + n * iter2 -> w);

 //                    link(iter2 -> to + n * (iter2 -> w ^ 1), iter -> to + n * iter -> w);

 //                }

         }

         for (R edge *iter = rt[i]; iter; iter = iter -> next)

             if (iter -> w) link(i, iter -> to);

     }

     for (R int i = ; !fail && i <= n; ++i) if (!dfn[i]) tarjan(i, );

     if (fail)

     {

         puts("Impossible");

         return ;

     }

     for (R int i = ; i <= n; ++i) if (used[id[i]]) ans[++tot] = i;

     printf("%d\n", tot);

     std::sort(ans + , ans + tot + );

     for (R int i = ; i <= tot; ++i) printf("%d ", ans[i]);

     return ;

 }

巴特西

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

题目描述

输入格式

输出格式

题解

代码

最新文章

热门文章