HDU--3308 How Many Answers Are Wrong

末蓝、 2022-08-11 00:57 36阅读 0赞

这一道题是水题一道，但是我能说我做了将近三个小时吗。。。就是一直在纠结如何存储端点的值。在百思不得其解得的时候终于搜了一下，结果呵呵。把闭区间改成半开半闭区间不就完事了吗、、、剩下的完全就是加权并查集了。

下面的代码是让大的点做根，小的点做的是叶子，那么叶子的权值就是正值了。。。

#include <cstdio>
    #include <cstring>
    #include <cstdlib>
    #define N 200005
    int pa[N];
    __int64 rank[N];
    
    int find(int x)
    {
    	if(x!=pa[x])
    	{
    		int tmp=pa[x];
    		pa[x]=find(tmp);
    		rank[x]+=rank[tmp];
    	}
    	return pa[x];
    }
    
    int initial(int n)
    {
    	for(int i=0;i<=n;i++)
    	{
    		pa[i]=i;
    	}
    	memset(rank,0,sizeof(rank));//n在不大的情况下，它可能较费些时间
    }
    int main()
    {
    	int n,m,count;
    	while(scanf("%d%d",&n,&m)==2)
    	{
    		count=0;
    	initial(n);
    	while(m--)
    	{
    		int x,y;__int64 Rank;//防止出现超过2^31 int越界，当然unsigned也行，不过到边的感觉让我没有安全感
    		scanf("%d%d%I64d",&x,&y,&Rank);
    		--x;
    		int px=find(x),py=find(y);
    		if(px!=py)
    		{
    			pa[px]=py;//取较大的点做根
    			rank[px]=-rank[x]+rank[y]-Rank;//画一下，很容易明白
    		}
    		else
    		{
    			if(rank[y]-rank[x]!=Rank)
    			count++;
    		}
    	}
    	printf("%d\n",count);
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，36人围观）

还没有评论，来说两句吧...

相关阅读

相关 Again! There are tons of wrong answers!

我已经放弃挣扎，全部代码都是直接复制粘贴的，但还是报错！！！！啊啊啊啊要疯了 OK there is the thing 我把附录所有前后端的代码都贴进去了，然后，在end

忘是亡心i/ 2024年03月31日 17:02/ 0 赞/ 151 阅读

相关 [kuangbin带你飞]专题五并查集 D - How Many Answers Are Wrong（带权并查集）

D - How Many Answers Are Wrong 题目链接：[https://vjudge.net/contest/66964\problem/D][http

你的名字/ 2023年08月17日 15:41/ 0 赞/ 205 阅读

相关 HDU--3308 How Many Answers Are Wrong

这一道题是水题一道，但是我能说我做了将近三个小时吗。。。就是一直在纠结如何存储端点的值。在百思不得其解得的时候终于搜了一下，结果呵呵。把闭区间改成半开半闭区间不就完事了吗、、、

末蓝、/ 2022年08月11日 00:57/ 0 赞/ 37 阅读

相关 D - How Many Answers Are Wrong——种类并查集

Think: 1知识点：种类并查集+后缀和数组 2思考：当学习新的知识点的时候不理解的地方应该动手实现在纸上模拟实现进而提高理解 [vjudge题目链接][vjudg

Bertha 。/ 2022年06月12日 11:50/ 0 赞/ 260 阅读

相关 HDU - 1213 - How Many Tables

-------------------- 题目连接：[http://acm.hdu.edu.cn/showproblem.php?pid=1213][http_acm.hdu

梦里梦外;/ 2022年06月10日 00:09/ 0 赞/ 264 阅读

相关 HDU-How Many Tables

How Many Tables Problem Description Today is Ignatius' birthday. He invites

女爷i/ 2022年05月28日 01:10/ 0 赞/ 285 阅读

相关【3038 HDU】How Many Answers Are Wrong（带权并查集）

题目：[点击打开题目链接][Link 1] 题意：给你一个n和一个m，n代表n个数，m代表m次询问，每次询问给你一个a，b，s，代表第a个数到第b个数的和是s，让你输出m次询

爱被打了一巴掌/ 2022年05月09日 11:36/ 0 赞/ 263 阅读

相关 HDU-3038.How Many Answers Are Wrong(带权并查集)

\[3038.How Many Answers Are Wrong)([http://acm.hdu.edu.cn/showproblem.php?pid=3038][htt

素颜马尾好姑娘i/ 2022年03月02日 11:18/ 0 赞/ 243 阅读

相关 HDU-1213-How Many Tables

链接：https://vjudge.net/problem/HDU-1213 题意：给n个人m个连通，求有几组思路：并查集模板代码：

女爷i/ 2021年12月24日 05:05/ 0 赞/ 303 阅读

相关 HDU-3038-How Many Answers Are Wrong【带权并查集】题解

目录 1.题目 2.题意 3.思路 4.代码 1.题目 TT

灰太狼/ 2021年08月29日 23:11/ 0 赞/ 382 阅读