hdu3047Zjnu Stadium 带权并查集

分类：并查集

并查集

;const int maxn = 50010 ;int F[maxn] ;int v[maxn] ;int n , m ;int find(int x){if(x == F[x])return F[x] ;int t = F[x] ;F[x] = find(t) ;v[x] += v[t] ;return F[x] ;}bool join(int x , int y , int num){int fx = find(x) ;int fy = find(y) ;if(fx == fy&&v[y] != v[x] + num)return false ;;else{if(v[x] + num > v[y]){F[fy] = fx;v[fy] = v[x] + num – v[y] ;}else{F[fx] = fy ;v[fx] = v[y] – (v[x] + num) ;}return true ;}}int main(){//freopen(“in.txt” ,”r” , stdin) ;while(~scanf(“%d%d” ,&n , &m)){for(int i = 1;i <= n;i++)F[i] = i ,v[i] = 0;int ans = 0 ;while(m–){int a , b , x ;scanf(“%d%d%d” ,&a , &b , &x) ;if(!join(a , b , x))ans++ ;}cout<<ans<<endl;}return 0 ;}

上一篇hdu4003Find Metal Mineral 树形dp+分组背包

顶0踩0

偶尔被惊鸿一瞥的美丽吸引;或者走进一条深沉深沉的巷道，

相关文章：

你感兴趣的文章：

标签云：