2019年湘潭大学程序设计竞赛-G Truthman or Fakeman

古城微笑少年丶 2022-01-25 16:43 151阅读 0赞

## 题目：   有n个人在玩一个身份扮演的游戏。   把这n个人编号为1,2,3...n。   其中每个人会扮演下面两种身份中的一种:   Truthman:当某个人扮演Truthman时，这个人只会说真话。   Fakeman:当某个人扮演Fakeman时，这个人只会说假话。   这n个人是互相知道身份的，但是Casya作为一个旁观者不知道任何一个人的身份。   为了让Casya有可能推断这些人的身份，这n个人说了m句话。   每句话的内容只包含某人对某人身份的一条描述，且被Casya记录为以下形式:   u,v,0 -- u认为v是一个Fakeman;   u,v,1 -- u认为v是一个Truthman;   当然这些话不一定都是真话，这取决于说话的人的身份。   但是可以肯定的是身份只有两种，也就是说某个人不是Truthman就是Fakeman。   Casya想知道不违反上面的条件和记录最少有多少个Fakeman，除此之外他还想得到一组在此情况下的一组合理的解—即所有人的身份。或者确定记录本来就是矛盾的所以没有任何符合条件的解。 ##

## 分析：如果A说B是Truthman 那么A和B是同一个团体，如果A说B是Fakeman，那么A和B是不同的两个团体，这两个条件只需在图上建立一个权值标记就行了，对于一个联通块，确定一个点的性质之后，整个联通块的每个点的性质就都确定了。只要将较大的那个定义为Truthman就好了，用dfs遍历连通块，如果一开始设为Truthman的团体较小 那就再dfs一遍取反。 ##

## 补充：这题也可以用种类并查集来做，可以参考[https://blog.csdn.net/weixin\_43849505/article/details/90082395][https_blog.csdn.net_weixin_43849505_article_details_90082395] ##

## [https://blog.csdn.net/qq\_42936517/article/details/90021825][https_blog.csdn.net_qq_42936517_article_details_90021825] ##

代码：

# #

#include <bits/stdc++.h>
    const int N = 1e5 + 5;
    using namespace std;
    int t,n,m,vs[N],a[N],flag,s1,s2;
    struct nd{
        int v,w;
    };
    vector<nd> e[N];
    
    void dfs(int u) {
        vs[u]=1;
        if(a[u]) s1++;
        else s2++;
        for(int i=0;i<e[u].size();i++) {
            int v=e[u][i].v,w=e[u][i].w;
            if(!vs[v]) {
                if(w) a[v]=a[u];
                else a[v]=a[u]^1;
                dfs(v);
            }else if((w&&a[u]!=a[v])||(w==0&&a[u]==a[v])) flag=1;
        }
    }
    
    void dfs2(int u) {
        vs[u]=2,a[u]^=1;
        for(int i=0;i<e[u].size();i++) {
            int v=e[u][i].v;
            if(vs[v]==1) {
                dfs2(v);
            }
        }
    }
    
    int main () {
        while (~scanf("%d",&t)) {
    	    while(t--) {
                scanf("%d%d",&n,&m);
                for(int i=1;i<=n;i++) e[i].clear();
                memset(vs,0,sizeof(vs));
                memset(a,0,sizeof(a));
                flag=0;
                for(int i=1,u,v,w;i<=m;i++) {
                    scanf("%d%d%d",&u,&v,&w);
                    if(w) e[u].push_back({v,1}),e[v].push_back({u,1});
                    else e[u].push_back({v,0}),e[v].push_back({u,0});
                }
                for(int i=1;i<=n;i++) {
                    if(!vs[i]) {
                        a[i]=1,s1=s2=0;
                        dfs(i);
                        if(s1<s2) dfs2(i);
                    }
                }
                if(flag) printf("-1\n");
                else {
                    for(int i=1;i<=n;i++)
                        printf("%d",a[i]==1);
                    printf("\n");
                }
    	    }
        }
        return 0;
    }

[https_blog.csdn.net_weixin_43849505_article_details_90082395]: https://blog.csdn.net/weixin_43849505/article/details/90082395
[https_blog.csdn.net_qq_42936517_article_details_90021825]: https://blog.csdn.net/qq_42936517/article/details/90021825