Farmer John ordered a high speed connection for his farm and is going to share his connectivity with the other farmers. To minimize cost, he wants to lay the minimum amount of optical fiber to connect his farm to all the other farms.
Given a list of how much fiber it takes to connect each pair of farms, you must find the minimum amount of fiber needed to connect them all together. Each farm must connect to some other farm such that a packet can flow from any one farm to any other farm.
The distance between any two farms will not exceed 100,000.
Input
The input includes several cases. For each case, the first line contains the number of farms, N (3 <= N <= 100). The following lines contain the N x N conectivity matrix, where each element shows the distance from on farm to another. Logically, they are N lines of N space-separated integers. Physically, they are limited in length to 80 characters, so some lines continue onto others. Of course, the diagonal will be 0, since the distance from farm i to itself is not interesting for this problem.Output
For each case, output a single integer length that is the sum of the minimum length of fiber required to connect the entire set of farms.Sample Input
4 0 4 9 21 4 0 8 17 9 8 0 16 21 17 16 0
Sample Output
28
题意：有n个点，点与点之间有距离，以n*n的形式给出，问在保证所有的点都连接在一起的情况下，最小的距离和是多少，注意输入有多组数据
思路：最小生成树的典型题，套用样板就可以，由于该题给的是邻接矩阵输入的图，所有我用的是Prim算法，用Kruskal算法可能会超时
代码：
1 #include <cstdio>
2 #include <fstream>
3 #include <algorithm>
4 #include <cmath>
5 #include <deque>
6 #include <vector>
7 #include <queue>
8 #include <string>
9 #include <cstring>
10 #include <map>
11 #include <stack>
12 #include <set>
13 #include <sstream>
14 #include <iostream>
15 #define mod 998244353
16 #define eps 1e-6
17 #define ll long long
18 #define INF 0x3f3f3f3f
19 using namespace std;
20
21 //存放地图
22 int ma[100][100];
23 //lowcost存放到起点的距离
24 //mst表示i指向的点，
25 int lowcost[100],mst[100];
26 //n表示点数
27 int n;
28 //初始化地图
29 void init()
30 {
31 for(int i=0;i<=n;i++)
32 {
33 for(int j=0;j<=n;j++)
34 {
35 //本地到本地的权值为0，到其他点的权值为无穷
36 if(i==j)
37 {
38 ma[i][j]=0;
39 }
40 else
41 {
42 ma[i][j]=INF;
43 }
44 }
45 }
46 }
47 //u表示起点
48 int prim(int u)
49 {
50 //ans表示树上所有边的权值和
51 int ans=0;
52 //初始化lowcost,mst
53 for(int i=1;i<=n;i++)
54 {
55 //将所有指向起点的边录入lowcost中
56 lowcost[i] = ma[u][i];
57 //所有的点都指向起点
58 mst[i]=u;
59 }
60 //起点已在树上，所以为-1
61 mst[u] = -1;
62 //遍历其他n-1个点
63 for(int i=1;i<n;i++)
64 {
65 //当前最小权值为INF
66 int mi=INF;
67 //当前最小值指向的点是-1
68 int v=-1;
69 //遍历所有的点
70 for(int j=1;j<=n;j++)
71 {
72 //如果该点不在树上，且该点到起点的距离小于当前最小权值
73 if(mst[j]!=-1&&lowcost[j]<mi)
74 {
75 //记录这个较小的点和权值
76 v=j;
77 mi=lowcost[j];
78 }
79 }
80 //v！=-1表示在所有与树连接的最小权值
81 if(v!=-1)
82 {
83 //将这个点标记
84 mst[v]=-1;
85 //累计这个边的权值
86 ans+=lowcost[v];
87 //遍所有的点
88 for(int j=1;j<=n;j++)
89 {
90 //如果j不在树上且j到树上的距离比j到v的距离大
91 //更新这个数据，并将mst[j]指向v
92 if(mst[j]!=-1&&lowcost[j]>ma[v][j])
93 {
94 lowcost[j]=ma[v][j];
95 mst[j]=v;
96 }
97 }
98 }
99 }
100 //返回树上所有边的权值和
101 return ans;
102 }
103 int main()
104 {
105 while(scanf("%d",&n)!=EOF)
106 {
107 init();
108 for(int i=1;i<=n;i++)
109 {
110 for(int j=1;j<=n;j++)
111 {
112 scanf("%d",&ma[i][j]);
113 }
114 }
115 printf("%d\n",prim(1));
116 }
117 }