HDU-3038 How Many Answers Are Wrong 带权并查集

本文主要是介绍HDU-3038 How Many Answers Are Wrong 带权并查集，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://acm.hdu.edu.cn/showproblem.php?pid=3038

//题目大意：有n次询问，给出a到b区间的总和，问这n次给出的总和中有几次是和前面已近给出的是矛盾的？？
//权为i到p[i]的‘距离’
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
#define maxn 200020int n,m;
int p[maxn],weight[maxn];     //并查集祖先结点 并查集权值int find(int x)
{if( p[x] == x ) return x;int t = p[x];p[x] = find( p[x] );weight[x] += weight[t];return p[x];
}void merge( int x,int y,int a,int b,int v )
{if( x > y ){p[y] = x;weight[y] = weight[a]-v-weight[b];}else{p[x] = y;weight[x] = v + weight[b] - weight[a];}
}void init()
{memset( weight,0,sizeof(weight) );for( int i = 0; i <= n; i++ )   p[i] = i;
}int main()
{while(scanf("%d%d",&n,&m) != EOF){init();int a,b,v,re = 0;for(int i = 0;i < m;i++){scanf("%d%d%d",&a,&b,&v);a--;int x = find(a);int y = find(b);if(x == y && weight[a] != weight[b] + v){re++;}else if(x != y)merge(x,y,a,b,v);}printf("%d\n",re);}return 0;
}

这篇关于HDU-3038 How Many Answers Are Wrong 带权并查集的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---