hdu3047 带权并查集

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

带权并查集

#include <iostream>
#include <cstring>using namespace std;int father[50005];
int rank[50005];
int n,m;int find(int x)
{if (x == father[x])return x;int t = father[x];father[x] = find(father[x]);rank[x] = rank[x] + rank[t];return father[x];
}void init()
{memset(rank,0,sizeof(rank));for (int i=1; i<=n; i++)father[i] = i;
}int Union(int a,int b,int s)
{int x = find(a);int y = find(b);if (x == y){if (rank[a]+s != rank[b])return 0;else    return 1;}father[y] = x;rank[y] = rank[a]+s-rank[b];return 1;
}int main()
{while (cin>>n>>m){init();int sum = 0;for (int i=1; i<=m; i++){int a,b,s;cin>>a>>b>>s;if (!Union(a,b,s))sum++;}cout<<sum<<endl;}return 0;
}

这篇关于hdu3047 带权并查集的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---