題目大意：有n次詢問，給出a到b區(qū)間的總和，問這n次給出的總和中有幾次是和前面已近給出的是矛盾的

解題思路：這道題第一次接觸很難往并查集方向去思考。這里使用的并查集很靈活，不僅僅要記錄其父親節(jié)點(diǎn)，同時(shí)還要記錄該節(jié)點(diǎn)到父親節(jié)點(diǎn)的總和。在更新時(shí)，[l,r]要變成[l-1,r]，比如有區(qū)間[1,2],[3,4],在更新[3,4]時(shí)可以合并成一個(gè)完整區(qū)間[1,4]，并且在計(jì)算[l,r]區(qū)間的總和時(shí)，是用sum[r] - sum[l-1]來算的。所以這里是用[l-1,r]的原因。

參考博客：http://www.cnblogs.com/ziyi--caolu/p/3476968.html

#include<iostream> #include<cstdio> #include<cstring>const int maxn = 200005; int n,m,ans; int fa[maxn],rank[maxn];int find(int x) {if(fa[x] == x) return x;int tmp = fa[x];fa[x] = find(fa[x]);rank[x] += rank[tmp]; return fa[x]; }void Union(int x,int y,int k) {int fx = find(x);int fy = find(y);if(fx == fy){if(rank[y] - rank[x] != k) ans++;}else if(fx > fy){fa[fx] = fy;rank[fx] = rank[y] - rank[x] - k;}else{fa[fy] = fx;rank[fy] = rank[x] + k - rank[y];} }int main() {int l,r,k;while(scanf("%d%d",&n,&m)!=EOF){for(int i = 0; i <= n; i++)fa[i] = i, rank[i] = 0;ans = 0;for(int i = 1; i <= m; i++){scanf("%d%d%d",&l,&r,&k);l--;Union(l,r,k);}printf("%d\n",ans); }return 0; }

總結(jié)

以上是生活随笔為你收集整理的hdu 3038(种类并查集)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。