HDU 3047 Zjnu Stadium 帶權並查集

gg,y一下就是每一个点到根的距离用rank维护,,

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <queue>
#include <math.h>
#include <set>
using namespace std;
#define mod 1007
#define ll int
#define rank Rank
#define N 100100
ll n;
ll f[N], rank[N];
ll find(ll x){
    if(x==f[x]) return x;
    int t = f[x];
    f[x] = find(f[x]);
    rank[x] += rank[t];
    return f[x];
}
bool Union(int x, int y, int m){
    int fx = find(x), fy = find(y);
    if(fx==fy)
    {
        if(rank[x] + m != rank[y])
            return false;
        return true;
    }
    f[fy] = fx;
    rank[fy] = rank[x] + m -rank[y];
    return true;
}
void init(){
    for(int i = 0; i <= n; i++)
        f[i] = i, rank[i] = 0;
}
int main(){
	int i, j, u, v, d, que;
	while(~scanf("%d %d",&n,&que)) {
        init();
        int ans = 0;
        while(que--)
        {
            scanf("%d %d %d",&u,&v,&d);
            if(Union(u,v,d)==false)
                ans++;
        }
        cout<<ans<<endl;
	}
	return 0;
}
/*


*/


更多相关文章
  • 题目大意: 有n个人坐在zjnu体育馆里面,然后给出m个他们之间的距离, A B X, 代表B的座位比A多X. 然后求出这m个关系之间有多少个错误,所谓错误就是当前这个关系与之前的有冲突. 分析: 首先我们假设所有节
  • hdu  3635 Dragon Balls (帶權並查集)
    Dragon Balls Time Limit: 2/1 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 3363    Accepted Submission(s): 1304 Pr
  • hdu3047 Zjnu Stadium  HDU 3038 How Many Answers Are Wrong (帶權並查集)
    How Many Answers Are Wrong Time Limit: 2/1 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 3855    Accepted Submissi
  • hdu  3074  Zjnu Stadium (帶權並查集)
    Zjnu Stadium Time Limit: 2/1 MS (Java/Others)
  • HDOJ 3047 帶權並查集
    解题思路转自: http://blog.csdn.net/azheng51714/article/details/8500459 http://blog.csdn.net/acresume/article/details/7461238   有一个体育馆,座位呈环状,想象下,貌似体育馆都是这样的,每
  • hdu 1829A Bugs LIfe(簡單帶權並查集)
    题意:Bug有两种性别,异性之间才交往, 让你根据数据判断是否存在同性恋,输入有 t 组数据,每组数据给出bug数量n, 和关系数m, 以下m行给出相交往的一对Bug编号 a, b.只需要判断有没有,按题目要求输出.这题有点坑的地方在于输出上多了一行空行,不PE都没注意到. 思路: 用一个数组gen
  • 秋实大哥打游戏 Time Limit: 1 Sec  Memory Limit: 256 MB 题目连接 http://acm.uestc.edu.cn/#/contest/show/59 Description ”
  • 1 /* 2 题意:有N个城市, 每一个城市都有一个龙珠(编号与城市的编号相同),有两个操作 3 T A ,B 将标号为A龙珠所在城市的所有的龙珠移动到B龙珠所在城市中! 4 5 思路:并查集 (压缩路径的时候将龙珠
一周排行