hdu5176 樹上所有兩點間（最大值-最小值）和

這是民大學長之前出的一次題目，感覺題目不錯現在才寫題解=

化簡不難得到： sig(maxval[i]−minval[i])=sig(maxval)−sigma(minval)

如何求所有最大值和最小值呢，分别從大到小和從小到大排序利用并查集就行了，比較巧妙。

額==題目設了一些坑，一個是一個方向的并查集會爆棧，故手工開棧，另外一個是鑰匙用unsigned long long==

1 #pragma comment(linker,"/STACK:16777216")
 2 #include<stdio.h>
 3 #include<string.h>
 4 #include<algorithm>
 5 using namespace std;
 6 #define LL long long
 7 #define uLL unsigned long long
 8 struct dian{
 9   uLL x,y,w;
10 }a[150005];
11 uLL father[150005],num[150005],n;
12 int cmp1(dian n1,dian n2)
13 {
14   return n1.w<n2.w;
15 }
16 int cmp2(dian n1,dian n2)
17 {
18   return n1.w>n2.w;
19 }
20 uLL find(uLL x)
21 {
22   if (x!=father[x]) father[x]=find(father[x]);
23   return father[x];
24 }
25 uLL work()
26 {
27   uLL ans=0,i,f1,f2;
28   for (i=1;i<=n;i++) 
29   {
30     father[i]=i;
31     num[i]=1;
32   }
33   for (i=1;i<n;i++)
34   {
35     f1=find(a[i].x); f2=find(a[i].y);
36     ans+=num[f1]*num[f2]*a[i].w;
37     father[f1]=f2;
38     num[f2]+=num[f1];
39   }
40   return ans;
41 }
42 int main()
43 {
44   uLL t=0,ans1,ans2,i;
45   while (~scanf("%I64u",&n))
46   {
47     for (i=1;i<n;i++) 
48       scanf("%I64u%I64u%I64u",&a[i].x,&a[i].y,&a[i].w);
49     sort(a+1,a+n,cmp1);
50     ans1=work();
51     sort(a+1,a+n,cmp2);
52     ans2=work();
53     printf("Case #%I64u: %I64u\n",++t,ans1-ans2);
54   }
55   return 0;
56 }      

View Code

題目連結：http://acm.hdu.edu.cn/showproblem.php?pid=5176

轉載于:https://www.cnblogs.com/xiao-xin/articles/4307704.html