Agri-Net POJ - 1258 最小生成树值Prim算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了Agri-Net POJ - 1258 最小生成树值Prim算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4354字，纯文字阅读大概需要7分钟。

内容图文

Farmer John has been elected mayor of his town! One of his campaign promises was to bring internet connectivity to all farms in the area. He needs your help, of course.?
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 }

 

内容总结

以上是互联网集市为您收集整理的Agri-Net POJ - 1258 最小生成树值Prim算法全部内容，希望文章能够帮你解决Agri-Net POJ - 1258 最小生成树值Prim算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---