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

本文主要是介绍2019年湘潭大学程序设计竞赛-G Truthman or Fakeman，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：
有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/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;
}

 

这篇关于2019年湘潭大学程序设计竞赛-G Truthman or Fakeman的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---