HDU-3038How Many Answers Are Wrong权值并查集
2024-09-02 17:49:39
题意:输入一连串的区间和,问和前面的矛盾个数;
思路:我在做专题,知道是并查集,可是还是不知道怎么做,学了一下权值并查集和大佬的优秀思路,感觉回了一点;
具体就是 在并查集的基础上,加上val【】数组用来记录区间和,而原来的fa【】数组表示的是这个数能到达的最左边的下标;
下面是ac代码
#include <cstdio>
#include <algorithm>
using namespace std; const int maxn = ;
int val[maxn],fa[maxn],n,m,ans=;//fa记录下标所能到达最左端(),val表示前缀和 void init(){
for(int i=;i<=n;i++)
{
fa[i] = i;
val[i]=;
}
} int find (int x)
{
if(fa[x]==x)return x;
else
{
int fn = find(fa[x]);
val[x] +=val[fa[x]];
return fa[x] = fn;
}
}
void uni(int a,int b,int s)
{
int px = find(a);
int py = find(b);
if(px==py) //只有左区间相同是才能比较
{
if(val[b]-val[a]!=s)ans++;
}
else
{
fa[py] = px;
val[py] = val[a] + s - val[b];
}
}
int main(){
while(~scanf("%d%d",&n,&m))
{
init();
ans = ;
for(int i=;i<=m;i++)
{
int a,b,s;
scanf("%d%d%d",&a,&b,&s);
a--;
uni(a,b,s);
}
printf("%d\n",ans);
}
return ;
}
最新文章
- 一道返回num值的小题目
- BZOJ1090: [SCOI2003]字符串折叠
- OCJP(1Z0-851) 模拟题分析(一)11
- RMAN duplciate 准备时,需要检查的target数据库参数内容
- MUI - 图片预览(perviewimage)的优化
- HTML的列表标签
- Python调用Webservice、访问网页
- MVVM架构的一次实践,重写iOS头条客户端
- [PWA] 6. Hijacking response
- 深入浅出理解QTimeLine类
- MySQL库目录下db.opt文件的作用
- js获取url中的参数方法
- ConstraintLayoutDemo【约束性布局知识梳理】【基于1.1.3】
- 搭建IIS并配置网站之旅
- 一个方法教你认识ref(简单易懂)
- Burnside引理的感性证明
- 【python练习题】程序15
- [爬虫]采用Go语言爬取天猫商品页面
- Pandas 基础(8) - 用 concat 组合 dataframe
- unittest框架assert断言