codeforces 747 div2 D The Number of Imposters

2021-10-18

字数统计: 693字 | 阅读时长≈ 3分

题目大意

有\(n\)个人，每个人的身份都是以下两个中的一个：\(imposter\)，\(crewmate\)。

一共有\(m\)个陈述，形如： \(x\) \(y\) \(imposter/crewmate\)，表示，\(x\)说\(y\)的身份是\(imposter/crewmate\)

注意，\(imposter\)只会说谎，\(crewmate\)只会说实话。

求：\(imposter\)最多可能有多少个。

思路

像这种划分阵营的题，我们无需知道每个人属于哪个阵营，只需知道哪些人属于同一个阵营

对于上面的两种陈述：

\(x\) \(y\) \(imposter\)，那么显然\(x\)和\(y\)属于不同的阵营
\(x\) \(y\) \(crewmate\)，那么\(x\)和\(y\)属于相同阵营

那么我们用\(0\)和\(1\)代表两个不同阵营（仅用于表示哪些人在同一阵营），用来表示点的权值。

我们建一个图，当出现情况1时，我们从\(x\)向\(y\)连一条权值为\(1\)的双向边，出现情况2时，我们\(x\)向\(y\)连一条权值为\(0\)的双向边。

那么之后我们可以遍历整张图，通过边权值与当前点的权值，通过异或边权，来判断下一个点的权值。

即，通过遍历，来判断能否构造出满足题意得阵营分配。

比如当前点权值为\(0\)通过一个边权为\(1\)的边，连向一个还未访问的点，那么新的点的权值就是\(0xor1=1\)。（属于两个不同阵营）

当然如果这个点被访问过了，我们需要看一下它的权值是否是\(0 xor 1=1\),如果不是，那么显然就出现矛盾了，输出\(-1\)。

代码

#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;

const int maxN = 2e5 + 7, maxM = 5e5 + 7;

int T, n, m, id[maxN], sum[3];
bool succ;

struct Edge {
    Edge(int _to, int _identity) {
        to = _to;
        identity = _identity;
    }
    int to, identity;
};

vector<Edge> e[maxM];

inline void init()
{
    for(int i = 1; i <= (n + m); ++i)
        e[i].clear();
    memset(id, -1, sizeof(id));
}

void dfs(int now)
{
    sum[id[now]]++;
    for(int i = 0; i < e[now].size(); ++i) {
        if(id[e[now][i].to] == -1) {
            id[e[now][i].to] = id[now] ^ e[now][i].identity;
            dfs(e[now][i].to);
        }
        else if(id[e[now][i].to] != (id[now] ^ e[now][i].identity)) {
            succ = false;
        }
    }
}

inline void work()
{
    init();
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; ++i) {
        char s[11]; int x, y;
        scanf("%d%d%s", &x, &y, s);
        if(s[0] == 'c') {
            e[x].push_back(Edge(y, 0));
            e[y].push_back(Edge(x, 0));
        }
        else {
            e[x].push_back(Edge(y, 1));
            e[y].push_back(Edge(x, 1));
        }
    }
    int ans = 0; succ = true;
    for(int i = 1; i <= n; ++i) {
        if(id[i] == -1) {
            sum[0] = sum[1] = 0;
            id[i] = 0;
            dfs(i);
            ans += max(sum[0], sum[1]);
        }
    }
    if(succ)
        printf("%d\n", ans);
    else
        printf("-1\n");
}

int main()
{
    scanf("%d", &T);
    while(T--) {
        work();
    }
}

本文作者： 水蓝络合物
本文链接： https://miku39393939.github.io/2021/10/18/codeforces-747-div2-D/
版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！