POJ 1182 食物链 +POJ 2492 A Bug's Life 种类并查集
发布日期:2021-08-16 13:28:01 浏览次数:34 分类:技术文章

本文共 2513 字,大约阅读时间需要 8 分钟。

膜大牛~写的超好,很详细,对于偏移量的确定也有讲解~

记得用scanf……cin……T了……orz

#include
     
      #include
      
       using namespace std;const int N = 5e4 + 5;struct node {
       
int pre;
int relation;};node p[N];int n, d,k, x, y,ans;void init(int n){
for (int i = 0; i <= n; i++)
{
p[i].pre = i;
p[i].relation = 0;
}}int findx(int x)  //带劝啥的还是老老实实用递归……{
if (x == p[x].pre)
 return x;
int temp = p[x].pre;
p[x].pre = findx(temp);
p[x].relation = (p[x].relation + p[temp].relation) % 3;
return p[x].pre;}void unionn(int a, int b){
x = findx(a);
y = findx(b);
if (x != y)
{
p[y].pre = x;
p[y].relation = (3+ p[a].relation+d-1-p[b].relation) % 3;
}
else
{
if (d == 1 && p[a].relation != p[b].relation)
ans++;
else if (d == 2 && (3 - p[a].relation + p[b].relation) % 3 != d - 1)
ans++;
}}int main(){
scanf("%d%d", &n, &k);
init(n);
ans = 0;
while (k--)
{
scanf("%d%d%d", &d, &x,&y);
if (x > n || y > n) ans++;
else if (x == 2 && x == y) ans++;
else unionn(x, y);
}
printf("%d\n", ans);
return 0;}

这个要比食物链简单很多,只需要区分♂♀两类,emmmm其实上一个也可以用下面的方法做

#include
     
      #include
      
       using namespace std;int n, t,k, a, b,flag;int pre[4005];void init(int n){
       
for (int i=0; i <= 2*n; i++)
pre[i] = i;}int findx(int x){
if (x == pre[x]) return x;
int r = pre[x];
pre[x] = findx(r);
return pre[x];}void unionn(int a, int b){
int x = findx(a), y = findx(b);
if(x!=y)
pre[y] = x;}bool judge(int x, int y){
if (findx(x) == findx(y)) return 0;
else return 1;}int main(){
scanf("%d", &t);
int cnt = 1;
while (t--)
{
scanf("%d%d", &n, &k);
init(n);
flag = 0;
for (int i = 0; i < k; i++)
{
scanf("%d%d", &a, &b);
if (judge(a, b) || judge(a + n, b + n))
{
unionn(a, b+n);
unionn(a + n, b);
}
else flag = 1;
}
if(cnt!=1)   //不要忘记换行orz
 puts("");
if (flag)
{
printf("Scenario #%d:\n", cnt++);
puts("Suspicious bugs found!");
 }
else
{
printf("Scenario #%d:\n", cnt++);
puts("No suspicious bugs found!");
}
}
return 0;}

 

转载于:https://www.cnblogs.com/Egoist-/p/7783636.html

转载地址:https://blog.csdn.net/weixin_30807779/article/details/98237643 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:下一波债市行情即将启动
下一篇:Linux驱动之定时器在按键去抖中的应用

发表评论

最新留言

哈哈,博客排版真的漂亮呢~
[***.249.79.50]2022年04月27日 05时21分06秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

最新文章