?

How Many Answers Are Wrong HDU - 3038? 點擊打開鏈接 題意：現在有n個數（你并不知道這n個數是什么），m次查詢，每次查詢給出u，v，w。表示從第u個數到第v個數的和為w。 問，在這些查詢中，有多少個是錯誤的（即有沖突）。 思路：從第u個數到第v個數的和其實可以理解為，第u-1個數到v個數之間的和。那么，就可以把和當成一種關系，利用帶權并查集來維護這種關系。u-1節點為根，v的權值為第u-1個數到v個數之間的和。這里需要理解一下的是，在Find函數和unite（合并）函數里面，有兩個關系域的轉移方程（暫且這么叫他吧） ①p[x].relation+=p[tmp].relation ②p[root2].relation=p[x].relation+relation-p[y].relation 這兩個方程需要自己帶入一兩個例子才能推得出來，所以不要憐惜你的紙和筆！！！一定要自己推一下 1 #include<iostream> 2 #include<cstring> 3 #include<algorithm> 4 #include<cstdio> 5 using namespace std; 6 const int Max=200005; 7 typedef struct node//par表示父親節點，relation表示關系，即權值 8 { 9 int par,relation; 10 }node; 11 node p[Max]; 12 int n,m,ans; 13 void init()//初始化，父親為自己，自己到自己的距離為0 14 { 15 ans=0; 16 for(int i=1;i<=n;i++){ 17 p[i].par=i; 18 p[i].relation=0; 19 } 20 } 21 int Find(int x)//路徑壓縮 22 { 23 if(x==p[x].par) 24 return x; 25 int tmp=p[x].par; 26 p[x].par=Find(tmp); 27 p[x].relation+=p[tmp].relation;//關系域的轉移方程一 28 return p[x].par; 29 } 30 void unite(int x,int y,int relation) 31 { 32 int root1=Find(x); 33 int root2=Find(y); 34 if(root1!=root2){//如果根不相同，那么，把root2連到root1上即合并操作 35 p[root2].par=root1; 36 p[root2].relation=p[x].relation+relation-p[y].relation;//關系域的轉移方程二 37 } 38 else{//如果根相同，則不用合并，那么進行判斷，看給出的區間的和是否有沖突，有的話ans++ 39 if(p[y].relation-p[x].relation!=relation) 40 ans++; 41 } 42 } 43 int main() 44 { 45 while(~scanf("%d%d",&n,&m)){ 46 int u,v,w; 47 init(); 48 for(int i=0;i<m;i++){ 49 scanf("%d%d%d",&u,&v,&w); 50 u-=1;//從第u個數到第v個數的和理解為，第u-1個數到v個數之間的和 51 unite(u,v,w); 52 } 53 printf("%d\n",ans); 54 } 55 return 0; 56 } View Code

?

?

?

轉載于:https://www.cnblogs.com/Levi-0514/p/9042485.html

總結

以上是生活随笔為你收集整理的How Many Answers Are Wrong HDU - 3038（带权并查集经典题，满满的都是注释）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。