约翰有N头奶牛，有一部分奶牛是真话奶牛，它们只说真话，而剩下的是假话奶牛，只说假话。有一天，约翰从奶牛的闲谈中陆续得到了M句话，第i句话出自第Xi头奶牛，它会告诉约翰第Yi头是一头真话奶牛还是假话奶牛。然而，约翰记性不好，他可能把这些话的内容记错了。请检查一下 约翰的记录是否会有矛盾，帮助他找到一个尽量大的K使得约翰记下的前K句话不矛盾。
第一行：两个整数 N 和 M ，1 ≤ N ≤ 1000; 1 ≤ M ≤ 10000
• 第二行到 M + 1 行：第 i + 1 行有两个整数：Xi 和 Yi，1 ≤ Xi， Yi ≤ N ，接下来有一个字符：
– 如果是 T ，表示 Xi 说 Yi 是真话奶牛；
– 如果是 L，表示 Xi 说 Yi 是假话奶牛；
单个整数，即表示题目描述中的K
4 3
1 4 L
2 3 T
4 1 T
2
解释
前两句没有矛盾, 但第一句和第三句存在矛盾
sol:
题目说的是前k个。。
并查集判断，如果一个点为真或为假时它的祖先相同，则矛盾了。
#include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #include<queue> #include<cmath> #include<set> using namespace std; const int N=2*1100,M=11000; int n,m,fa[N]; char s[10]; int findfa(int x) { if(fa[x]==x) return x; return findfa(fa[x]); } int main() { // freopen("a.in","r",stdin); freopen("truth.in","r",stdin); freopen("truth.out","w",stdout); scanf("%d%d",&n,&m); for(int i=1;i<=2*n;i++) fa[i]=i; int x,y,k=0,bk=1; for(int i=1;i<=m;i++) { scanf("%d%d",&x,&y); scanf("%s",s); if(s[0]=='L') { fa[findfa(x)]=findfa(n+y); fa[findfa(n+x)]=findfa(y); } else { fa[findfa(x)]=findfa(y); fa[findfa(n+x)]=findfa(n+y); } if(findfa(y)==findfa(n+y)) bk=0; if(bk) k++; } printf("%d\n",k); return 0; }
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。