感谢@远山淡影 大佬指出问题
题目描述
动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。
A吃B， B吃C，C吃A。
现有N个动物，以1－N编号。
每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。
有人用两种说法对这N个动物所构成的食物链关系进行描述：
第一种说法是”1 X Y”，表示X和Y是同类。
第二种说法是”2 X Y”，表示X吃Y。
此人对N个动物，用上述两种说法，一句接一句地说出K句话，这K句话有的是真的，有的是假的。
当一句话满足下列三条之一时，这句话就是假话，否则就是真话。
1） 当前的话与前面的某些真的话冲突，就是假话；
2） 当前的话中X或Y比N大，就是假话；
3） 当前的话表示X吃X，就是假话。
你的任务是根据给定的N和K句话，输出假话的总数。
输入格式
第一行是两个整数N和K，以一个空格分隔。
以下K行每行是三个正整数 D，X，Y，两数之间用一个空格隔开，其中D表示说法的种类。
若D=1，则表示X和Y是同类。
若D=2，则表示X吃Y。
输出格式
只有一个整数，表示假话的数目。
数据范围
1≤N≤50000
0≤K≤100000
样例
输入样例：
100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5
输出样例：
3
并查集(拓展域)
这道题目我们主要是要开三个拓展的域,也就是天敌域,同类域,以及捕食域.
- 如果x,y是同类,但是x的捕食域有y,那么错误
- 如果x,y是同类,但是x的天敌域有y,那么错误
- 如果x是y的天敌,但是x的同类域中有y,那么错误
- 如果x是y的天敌,但是x的天敌域中有y,那么错误
C++ 代码
//这里我们将三个域,分别转化为了n,n+n,n+n+n.因为读入方面特别烦.
#include <bits/stdc++.h>
using namespace std;
int fa[200000];
int n,m,k,x,y,ans;
int get(int x)
{
if(x==fa[x])
return x;
return fa[x]=get(fa[x]);
}
void merge(int x,int y)
{
fa[get(x)]=get(y);
}
int main()
{
cin>>n>>m;
for(int i=1;i<=3*n;i++)
fa[i]=i;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&k,&x,&y);
if(x>n || y>n)
ans++;
else if(k==1)
{
if(get(x)==get(y+n) || get(x)==get(y+n+n)) //如果x,y是同类,但是x是y的捕食中的动物,或者x是y天敌中的动物,那么错误.
ans++;
else
{
merge(x,y);
merge(x+n,y+n);
merge(x+n+n,y+n+n);
}
}
else
{
if(x==y || get(x)==get(y) || get(x)==get(y+n)) //x就是y,或者他们是同类,再或者是y的同类中有x
ans++;//都是假话
else
{
merge(x,y+n+n);//y的捕食域加入x
merge(x+n,y);//x的天敌域加入y
merge(x+n+n,y+n);//x的捕食域是y的同类域.
}
}
}
cout<<ans<<endl;
}
//x是同类域.
//x+n是捕食域
//x+n+n是天敌域
领域展开~无量假话
if(x==y || get(x)==get(y) || get(x)==get(y+n)) //x就是y,或者他们是同类,再或者是y的同类中有x中标记是否有误？ 不应该写成x就是y,或者他们是同类,再或者是y的捕食域中有x
俺也感觉这里好像有点小问题
merge(x,y+n+n);//y的捕食域加入x -> y的天敌域加入x merge(x+n,y);//x的天敌域加入y -> x的捕食域加入y merge(x+n+n,y+n);//x的捕食域是y的同类域. -> x的天敌域可以捕食y的捕食域是不是得这样修改一下
我觉得是这样， 可能打错了。
大佬思路很清晰 学到了不少
但是请问这三句话的注释是不是有问题呢？
merge(x,y+n+n); // y的捕食域加入x merge(x+n,y); // x的天敌域加入y merge(x+n+n,y+n); // x的捕食域是y的同类域.我认为应该改为
merge(x,y+n+n); // y的天敌域加入x merge(x+n,y); // x捕食域加入y merge(x+n+n,y+n); // x的天敌域为y的捕食域#include <iostream> using namespace std; int n, k; int p[150010]; int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); } int main() { cin >> n >> k; // x是同类域. x+n是捕食域. x+n+n是天敌域 for (int i = 1; i <= 3 * n; i ++ ) p[i] = i; int res = 0; while (k -- ) { int d, x, y; cin >> d >> x >> y; if (x > n || y > n) { res ++ ; continue; } if (d == 1) // xy是同类.即xy是同类域 { // 则x是y的捕食域||x是y的天敌域 假 if (find(x) == find(y + n) || find(x) == find(y + n + n)) { res ++ ; continue; } // 更新xy三个域的关系 p[find(x)] = find(y); // x的同类域=y的同类域 p[find(x + n)] = find(y + n); // x的捕食域=y的捕食域 p[find(x + n + n)] = find(y + n + n); // x的天敌域=y的天敌域 } else // x吃y.即x是y的天敌 { // 则x是y的同类域||x是y的捕食域 假 if (find(x) == find(y) || find(x) == find(y + n)) { res ++ ; continue; } // 更新xy三个域的关系 p[find(x)] = find(y + n + n); // x的同类域=y的天敌域 p[find(x + n)] = find(y); // x的捕食域=y的同类域 p[find(x + n + n)] = find(y + n); // x的天敌域=y的捕食域 } } cout << res << endl; return 0; }帮！
李哥的解释是对的.
非常清晰
%%%
大佬求助！我想用 fa[i] == -1 时表示根节点，稍微改了下代码。为什么会超内存？
//这里我们将三个域,分别转化为了n,n+n,n+n+n.因为读入方面特别烦. #include <bits/stdc++.h> using namespace std; int fa[200000]; int n,m,k,x,y,ans; int get(int x) { if(-1==fa[x]) return x; return fa[x]=get(fa[x]); } void merge(int x,int y) { fa[get(x)]=get(y); } int main() { cin>>n>>m; // for(int i=1;i<=3*n;i++) // fa[i]=i; //这里用-1表示根 memset(fa, -1, sizeof fa); for(int i=1;i<=m;i++) { scanf("%d%d%d",&k,&x,&y); if(x>n || y>n) ans++; else if(k==1) { if(get(x)==get(y+n) || get(x)==get(y+n+n)) //如果x,y是同类,但是x是y的捕食中的动物,或者x是y天敌中的动物,那么错误. ans++; else { merge(x,y); merge(x+n,y+n); merge(x+n+n,y+n+n); } } else { if(x==y || get(x)==get(y) || get(x)==get(y+n)) //x就是y,或者他们是同类,再或者是y的同类中有x ans++;//都是假话 else { merge(x,y+n+n);//y的捕食域加入x merge(x+n,y);//x的天敌域加入y merge(x+n+n,y+n);//x的捕食域是y的同类域. } } } cout<<ans<<endl; } //x是同类域. //x+n是捕食域 //x+n+n是天敌域我懂了，merge函数那里出了问题，如果x、y已经在同一个集合，按照那种思路，会构成环。改成下面即可：
void merge(int x,int y) { int i = get(x), j = get(y); if(i != j) fa[i] = j; }ORZ ORZ
%%%%%%%%%
nb，缪
大师我悟了
%%%%%%%%%’
好聪明的想法，耳目一新！
%%%%%
妙啊啊啊啊啊啊
给定一句话，如果
x，y动物不属于同一集合则，那么这句话一定为真吗？ 为什么？一定真。因为这道题对真话的判断就是如果无法根据话本身或前面的话判定为假，就是真话
为什么不能根据前面的话判定为假？
具体来说如果x和y的本身、天敌域和捕食域全都没有交集，就说明它们前面没有过任何有关的说法。
所以根据题目的意思，是真的。
光是本身不属于同一集合只能说明没有被说过是同类。其实并不能说明什么。
所以要看你对“x,y动物不属于同一集合”到底怎么理解。
谢谢你， 我再想想
‘’‘’
#include[HTML_REMOVED]
using namespace std;
const int N = 50010;
int n,m;
int p[N],d[N];
//找祖宗（并查集核心）
int find(int x){
//p[x]不是祖宗
if(p[x] != x){
int t = find(p[x]); //保存找到的祖宗，路径压缩（查）
d[x] +=d[p[x]]; //路径计算，爸爸的路径+爷爷（爸爸的爸爸）的路径
p[x] = t; //告诉孩子们祖宗是谁，路径压缩（合并）
} return p[x]; //返回祖宗}
int main(){
scanf("%d%d",&n,&m);//n：动物的总数，m：说话的总数 for(int i = 1; i<= n; i++)p[i] = i; //初始化，每个都是祖宗(没有合并) int res = 0; //统计谎话 while(m--){ int t, x, y; scanf("%d%d%d",&t,&x,&y);//t：1同类、2是x<-y（x吃y）；x：任意动物（数字）；y：任意动物（数字） if(x > n|| y > n) res ++;//谎话,规则2 else{ int px = find(x),py = find(y); //找x和y的到祖宗的距离 if(t == 1){//同类的情况下 if( px == py && (d[x] - d[y])% 3)res ++;//px== py是同一个祖宗（集合），(d[x]-d[y])%3！=0，说明不是同类，不符合t =1，谎话 else if( px != py){ //不是同一个祖宗，把他们归宗 p[px] = py; //将他们归为同一个祖宗（合并），px->py d[px] = d[y] - d[x]; //并计算他们之间的距离，这里y- x 表示x到y的距离 } } else{ //等于1的时候，吃与被吃 if( px == py && (d[x] - d[y] - 1)%3)res ++;//x吃y ,(d[x]-d[y]-1)%3！=0说明，他们不是被吃关系，谎话 else if(px != py){ //不是同一个祖宗，把他们归宗 p[px] = py; //将他们归为同一个祖宗（合并），px->py d[px] = d[y] + 1 - d[x];//并计算他们之间的距离，这里y- x 表示x到y的距离,+1表示被吃的关系 } } } } printf("%d\n",res); //输出谎话总数 return 0;}
‘’‘
借楼
因为读入方面特别烦hhh
为什么我用一个固定的常量
Q=5e4来表示这些x+Qx+Q+Q这些就不行？一定要用n？用固定的常量也是可以的，如果WA了的话，你可以看看是不是父节点初始化的时候没有把所有用到的域都包含进去
因为大佬用的是n，所以代码中初始化父节点为
for(int i = 1;i <= 3 * n;i++) fa[i] = i;
但如果你用的是固定常量，并且n小于你的固定常量Q时，3 * n无法包含所有用到的域
你可以试着把初始化父节点的代码改成
for(int i = 1;i <= 3 * Q;i++) fa[i] = i;
和虚拟内存很相似的感觉！（思考）
好像，动物a的三个域可以用 a a+n a+n+n表示