HDU 1233 还是畅通工程（最小生成树）

某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省*“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。

Input测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 )；随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。
当N为0时，输入结束，该用例不被处理。
Output对每个测试用例，在1行里输出最小的公路总长度。
Sample Input

Sample Output

3
5

题解：套模板

还是菜得一P啊

 1 #include <iostream>
 2 #include <algorithm>
 3 using namespace std;
 4 const int maxn=10005;
 5 int n,res,m;
 6 int par[maxn];
 7 struct node
 8 {
 9     int u,v,w;
10 }es[maxn];
11 int cmp(node x,node y)
12 {
13     return x.w<y.w;
14 }
15 void init()
16 {
17     for(int i=1;i<maxn;i++) par[i]=i;
18 }
19 int Find(int x)
20 {
21     if(par[x]==x) return x;
22     else return Find(par[x]);
23 } 
24 int deal()
25 {
26     init();
27     sort(es,es+m,cmp);
28     res=0;
29     for(int i=0;i<m;i++){
30         int u=es[i].u,v=es[i].v,w=es[i].w;
31         if(Find(u)==Find(v)) continue;
32         par[Find(u)]=Find(v);
33         res+=w;
34     }
35     return res;
36 }
37 int main()
38 {
39     while(cin>>n&&n){
40         m=n*(n-1)/2;
41         for(int i=0;i<m;i++){
42             cin>>es[i].u>>es[i].v>>es[i].w;
43         }
44         cout<<deal()<<endl;
45     }
46     return 0;
47 }

。。。。。。

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstring>
 4 #include <cstdio>
 5 #include <vector>
 6 #include <cstdlib>
 7 #include <iomanip>
 8 #include <cmath>
 9 #include <ctime>
10 #include <map>
11 #include <set>
12 #include <queue>
13 using namespace std;
14 #define lowbit(x) (x&(-x))
15 #define max(x,y) (x>y?x:y)
16 #define min(x,y) (x<y?x:y)
17 #define MAX 100000000000000000
18 #define MOD 1000000007
19 #define pi acos(-1.0)
20 #define ei exp(1)
21 #define PI 3.141592653589793238462
22 #define INF 0x3f3f3f3f3f
23 #define mem(a) (memset(a,0,sizeof(a)))
24 typedef long long ll;
25 ll gcd(ll a,ll b){
26     return b?gcd(b,a%b):a;
27 }
28 bool cmp(int x,int y)
29 {
30     return x>y;
31 }
32 const int N=10005;
33 const int mod=1e9+7;
34 int f[N];
35 struct edge
36 {
37     int u,v,w;
38 }a[N];
39 void init()
40 {
41     for(int i=1;i<=N;i++)
42         f[i]=i;
43 }
44 int find1(int x)
45 {
46     if(x!=f[x])
47         f[x]=find1(f[x]);
48     return f[x];
49 }
50 bool cmp1(edge a,edge b)
51 {
52     return a.w<b.w;
53 }
54 int main()
55 {
56     std::ios::sync_with_stdio(false);
57     int n,m;
58     while(scanf("%d",&n)&&n){
59         init();
60         m=n*(n-1)/2;
61         for(int i=0;i<m;i++)
62             scanf("%d %d %d",&a[i].u,&a[i].v,&a[i].w);
63         sort(a,a+m,cmp1);
64         int s=0;
65         for(int i=0;i<m;i++){
66             int u=a[i].u,v=a[i].v,w=a[i].w;
67             if(find1(u)==find1(v)) continue;
68             f[find1(u)]=find1(v);
69             s+=w;
70         }
71         printf("%d
",s);
72     }
73     return 0;
74 }

HDU 1233 还是畅通工程 （最小生成树 ）

相关推荐

HDU 1233 还是畅通工程（最小生成树）