HDU 5253 最小生成树 kruscal

Description

老 Jack 有一片农田，以往几年都是靠天吃饭的。但是今年老天格外的不开眼，大旱。所以老 Jack 决定用管道将他的所有相邻的农田全部都串联起来，这样他就可以从远处引水过来进行灌溉了。当老 Jack 买完所有铺设在每块农田内部的管道的时候，老 Jack 遇到了新的难题，因为每一块农田的地势高度都不同，所以要想将两块农田的管道链接，老 Jack 就需要额外再购进跟这两块农田高度差相等长度的管道。

现在给出老 Jack农田的数据，你需要告诉老 Jack 在保证所有农田全部可连通灌溉的情况下，最少还需要再购进多长的管道。另外，每块农田都是方形等大的，一块农田只能跟它上下左右四块相邻的农田相连通。

Input

第一行输入一个数字$T (T leq 10)$，代表输入的样例组数

输入包含若干组测试数据，处理到文件结束。每组测试数据占若干行，第一行两个正整数 $N, M (1 leq N, M leq 1000)$，代表老 Jack 有N行*M列个农田。接下来 N 行，每行 M 个数字，代表每块农田的高度，农田的高度不会超过100。数字之间用空格分隔。

Output

对于每组测试数据输出两行：

第一行输出："Case #i:"。i代表第i组测试数据。

第二行输出 1 个正整数，代表老 Jack 额外最少购进管道的长度。

Sample Input

4 3

9 12 4

7 8 56

32 32 43

21 12 12

2 3

34 56 56

12 23 4

Sample Output

Case #1:

Case #2:

题意：中文题意用最少的管道使得所有农田联通

题解：预处理出所有的相邻的农田间的高度差这个高度差也就是使得两块农田联通所需要的管道的长度

最小生成树 kruscal 处理

 1 #include<bits/stdc++.h>
 2 #include<algorithm>
 3 #define ll __int64
 4 #define mod 1e9+7
 5 #define PI acos(-1.0)
 6 #define bug(x) printf("%%%%%%%%%%%%%",x);
 7 #define inf 1e8
 8 using namespace std;
 9 int t;
10 int n,m;
11 struct node
12 {
13     int l;
14     int w;
15     int r;
16 }N[2000005];
17 int f[1000005];
18 int mp[1005][1005];
19 int jishu;
20 int flag;
21 bool cmp(struct node aa,struct node bb)
22 {
23     if(aa.w<bb.w)
24         return true ;
25     return false;
26 }
27 int find(int root)
28 {
29     if(root!=f[root])
30         return f[root]=find(f[root]);
31     else
32         return f[root];
33 }
34 void unio (int xx,int yy)
35 {
36     int xxx=find(xx);
37     int yyy=find(yy);
38     if(xxx!=yyy)
39         f[xxx]=yyy;
40 }
41 void kruscal()
42 {
43     int ans=0;
44     int gg=n*m;
45     for(int i=0;i<jishu;i++)
46     {
47 
48         int u=find(N[i].l);
49         int v=find(N[i].r);
50         if(u!=v)
51         {
52             gg--;
53             ans+=N[i].w;
54             unio(u,v);
55         }
56         if(gg==1)
57             break;
58     }
59     printf("Case #%d:
",flag++);
60     printf("%d
",ans);
61 }
62 int main()
63 {
64     while(scanf("%d",&t)!=EOF)
65     {
66         flag=1;
67         for(int i=1;i<=t;i++)
68         {
69             jishu=0;
70             scanf("%d %d",&n,&m);
71             for(int j=1;j<=n;j++)
72             {
73                 for(int k=1;k<=m;k++)
74                 {
75                     f[(j-1)*m+k]=(j-1)*m+k;
76                     scanf("%d",&mp[j][k]);
77                     if(k>1)
78                     {
79                     N[jishu].l=(j-1)*m+k-1;
80                     N[jishu].r=(j-1)*m+k;
81                     N[jishu++].w=abs(mp[j][k]-mp[j][k-1]);
82                     }
83                     if(j>1)
84                     {
85                     N[jishu].l=(j-2)*m+k;
86                     N[jishu].r=(j-1)*m+k;
87                     N[jishu++].w=abs(mp[j][k]-mp[j-1][k]);
88                     }
89                 }
90             }
91             sort(N,N+jishu,cmp);
92             kruscal();
93         }
94     }
95     return 0;
96 }