HDU3047-Zjnu Stadium-带权并查集

题意

给出n和m，n代表n个人，m代表接下去有m行数据需要进行判断。

接下去m行，每行给出数据x，y，z表示x的位置加上距离z就是y所在的位置。

输出有多少个是和前面的例子矛盾的，输出矛盾个数。

思路

这题是并查集的变形，也就是带权并查集，表示在俩俩合并的时候需要对于距离进行存储判断

注意

这题的样例自己纯推不太好推。

参考博客，可以看下这个博客的图，解释样例解释的很清楚：https://blog.csdn.net/hj1107402232/article/details/9921311

AC代码

#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
 typedef long long ll;
 const int N=50020;

 int f[N],d[N],n;

 void init()
 {
     for(int i=1;i<=n;i++)
     {
         f[i]=i;
         d[i]=0;
     }
 }
 int getf(int x)
 {
     if(f[x]==x)
         return x;
     else
     {
         int t=f[x];//找它的父节点
         f[x]=getf(f[x]);
         d[x]=d[x]+d[t];//d[x]（为x到根节点的距离）更新为它到它父节点的距离+父节点到根节点的距离
         return f[x];
     }
 }

 void merge(int x,int y)
 {
     int t1=getf(x);
     int t2=getf(y);
     if(t1!=t2)
         f[t2]=t1;
     return;
 }

 int main()
 {
     int m,x,y,z;
     while(~scanf("%d %d",&n,&m))
     {
         init();
         int ans=0;
         for(int i=0;i
图论

相关

图论---网络流

数的重心(图论深搜)

电子科技大学《图论及其应用》复习总结--第七章 图的着色

电子科技大学2017年《图论及其应用》试卷及答案

图论算法遍历基础

图论算法与模型（训练指南题库）

图论中的初始值

图论算法-最小生成树

LeetCode题解-07（简单图论）

图论学习笔记（二）

关于树（图论初步）

专题训练3-图论 - B - Learning Languages（并查集）

标签