P1546 最短网络 Agri-Net【MST】

题目背景

Farmer John 被选为他们镇的镇长！他其中一个竞选承诺就是在镇上建立起互联网，并连接到所有的农场。当然，他需要你的帮助。

题目描述

FJ 已经给他的农场安排了一条高速的网络线路，他想把这条线路共享给其他农场。为了用最小的消费，他想铺设最短的光纤去连接所有的农场。

你将得到一份各农场之间连接费用的列表，你必须找出能连接所有农场并所用光纤最短的方案。每两个农场间的距离不会超过 $10^5105。$

输入格式

第一行农场的个数

接下来是一个

输出格式

只有一个输出，其中包含连接到每个农场的光纤的最小长度。

输入输出样例

输入 #1

输出 #1

说明/提示

题目翻译来自NOCOW。

USACO Training Section 3.1

思路

　　黄题难度，建图跑一遍KRUSKAL就可以了，注意一下路压和边组要开N * N的

CODE

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 
 6 using namespace std;
 7 const int maxn = 1e3+7;
 8 
 9 ///把所有边排序，记第i小的边为:e[i](1 <= i < m)
10 ///初始化MST为空
11 ///初始化连通分量，让每个点自成一个独立的连通分量
12 ///for(int i = 0; i < m; i++) {
13 ///   if(e[i].u 和 e[i].v 不在同一个连通分量) {
14 ///     把边e[i]加入MST
15 ///     合并e[i].u 和 e[i].v 所在的连通分量
16 ///   }
17 ///}
18 
19 int fa[5050],n,m,ans,eu,ev,cnt;
20 
21 struct node{
22     int u, v, w;
23 }e[1000007];
24 
25 int a[maxn][maxn];
26 
27 bool cmp(node a, node b)
28 {
29     return a.w < b.w;
30 }
31 
32 int fid(int x)
33 {
34     return x == fa[x] ? x : fa[x] = fid(fa[x]);
35 }
36 
37 void init(int n)
38 {
39     for(int i = 1; i <= n; i++) {
40         fa[i] = i;
41     }
42     ans = 0;
43     cnt = 0;
44 }
45 
46 bool unite(int r1, int r2)///冰茶鸡
47 {
48     int fidroot1 = fid(r1), fidroot2 = fid(r2);
49     if(fidroot1 != fidroot2) {
50         fa[fidroot2] = fidroot1;
51         return true;
52     }
53     return false;
54 }
55 
56 void kruskal(int m)
57 {
58     sort(e+1, e+m+1, cmp);
59     for(int i = 1; i <= m; i++) {
60         eu = fid(e[i].u);
61         ev = fid(e[i].v);
62         if(eu == ev) {
63             continue;
64         }
65         ans += e[i].w;
66         fa[ev] = eu;
67         if(++cnt == n-1) {
68             break;
69         }
70     }
71 }
72 
73 int main()
74 {
75     scanf("%d",&n);
76     init(n);
77     for ( int i = 1; i <= n; ++i ) {
78         for ( int j = 1; j <= n; ++j ) {
79             scanf("%d",&a[i][j]);
80         }
81     }
82     m = 0;
83     for ( int i = 1; i <= n; ++i ) {
84         for ( int j = 1; j <= n; ++j ) {
85             if(i == j)
86                 continue;
87             else {
88                 e[++m].u = i, e[m].v = j;
89                 e[m].w = a[i][j];
90             }
91         }
92     }
93     ans = 0;
94     kruskal(m);
95     cout << ans << endl;
96     return 0;
97 }

View Code