yxy

用户名：dotcpp0787179

访问量：445

签　名：

竞赛交流论坛： blog.qzcy2.top 欢迎来撩！

等　　级
排　　名	1030
经　　验	3291
参赛次数	1
文章发表	23
年　　龄	1
在职情况	学生
学　　校	内江师范学院
专　　业	纳西妲系

　　自我简介：

我不会

TA的其他文章

[金银岛]自定义排序优先'均权'最大--我看题解都太复杂辣
浏览：48

杀到这九天十地无人敢称尊,直到身边再无一人能陪我征战,叶天帝不过如此
浏览：23

你可能喜欢

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

[食物链] 并查集 - NOI2001 提高组

　　作者: yxy　　　　发表时间：2024-10-07 18:32:11 浏览：22　|　评论：0　

原题链接：食物链[NOI2001]

# 并查集 路劲压缩
###### 根据题目将所有的动物分为 被捕食 天敌 竞争对手 三种类型 分别存放于 并查集的 三个位置 分别求各自所属的“连通块”

思路 ： 如果
1）当前的话与前面的某些真的话冲突，就是假话；
2）当前的话中X或Y比N大，就是假话；
3）当前的话表示X吃X，就是假话。
###### 之后给的任一一个满足以上三种情况 就行成悖论 也就是假话

##### 其实此题和正常的并查集一样 只是将动物分为三种不同的群体 就可以很轻松的判断出 当前的关系了

###### Code：
````cpp
#include <iostream>
#include <cstring>
#include <algorithm>
#define int long long  // 个人习惯 有备无患

using namespace std;
const int N = 300005;
int n , m;
int p[N] , ans;

int find(int x)   //路劲压缩 并
{
    if (x != p[x]) p[x] = find(p[x]);

return p[x];
}

inline void solve()
{
ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0); //关闭输入输出流
cin >> n >> m;

for (int i = 1 ; i <= n * 3 ; i ++ )  p[i] = i; // 0 - n , n + 1 - 2n , 2n + 1 - 3n 分别存储 三种不同的关系群

while ( m -- )
{
    int a , b , c;
    cin >> a >> b >> c;
    if (b > n || c > n)
    {
        ans ++;
        continue;
    }

if (a == 1)
    {
        if (find(n + b) == find(c) || find(2 * n + b) == find(c))
        {
            ans ++;
            continue;
        }
        else p[find(b)] = find(c) , p[find(b + n)] = find(c + n) , p[find(n + n + b)] = find(c + n + n); 
    }
    if (a == 2)
    {
        if (b == c)
        {
            ans ++;
            continue;
        }
        if (find(b) == find(c) || find(n + n + b) == find(c))
        {
            ans ++;
            continue;
        }
        
        p[find(b)] = find(n + n + c) , p[find(b + n)] = find(c) , p[find(b + n + n)] = find(c + n);
    }

}

cout << ans << endl;

}

signed main()
{
    solve();
    return 0;
}
````

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

yxy

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

简单的a+b （C语言代码）

[食物链] 并查集 - NOI2001 提高组

评论区

精彩推荐

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言训练-斐波纳契数列（C语言代码）

蓝桥杯历届试题-九宫重排（C++代码）

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

简单的a+b （C语言代码）

C二级辅导-计负均正（C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

字符逆序（C语言代码）

yxy

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

简单的a+b （C语言代码）

[食物链] 并查集 - NOI2001 提高组

评论区

精彩推荐

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言训练-斐波纳契数列 （C语言代码）

蓝桥杯历届试题-九宫重排 （C++代码）

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

简单的a+b （C语言代码）

C二级辅导-计负均正 （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

字符逆序 （C语言代码）

　　评论区

C语言训练-斐波纳契数列（C语言代码）

蓝桥杯历届试题-九宫重排（C++代码）

C二级辅导-计负均正（C语言代码）

字符逆序（C语言代码）