题目:
链接:点击打开链接
题意:
思路:
冲突的条件是:两个人坐在同一行,同时他们到根节点的差值等于他们之间的差值,这时就产生冲突了。于是我们可以用一个dist数组来保存节点到根的距离,而这个距离在路径压缩的时候更新一下就可以了,dist[x]+=dist[parent[x]]。然后就是合并后的距离,令r1=Find(u),r2=Find(v),于是合并时就有parent[r2]=r1,dist[r2]=dist[u]+w-dist[v]。
代码:
#include <iostream> #include <cstdio> #include <cstring> using namespace std; const int N = 50050; int n,m; int u,v,w; int root[N]; int dis[N]; int cnt; int findset(int x) { if(x == root[x]) return x; int temp = findset(root[x]); dis[x] += dis[root[x]]; return root[x] = temp; } int mergeset(int u,int v,int w) { int fx = findset(u); int fy = findset(v); if(fx == fy && dis[v] != dis[u]+w) return 1; root[fy] = fx; dis[fy] = dis[u] - dis[v] + w; return 0; } void init() { for(int i=0; i<=n; i++) { root[i] = i; dis[i] = 0; } cnt = 0; } int main() { //freopen("input.txt","r",stdin); while(scanf("%d%d",&n,&m) != EOF) { init(); for(int i=0; i<m; i++) { scanf("%d%d%d",&u,&v,&w); if(mergeset(u,v,w)) cnt++; } printf("%d\n",cnt); } return 0; }
战斗, 从不退缩;奋斗,永不停歇~~~~~~
hdu 3047 Zjnu Stadium (带权并查集),布布扣,bubuko.com
原文:http://blog.csdn.net/u013147615/article/details/30351179