poj 1258 Agri-Net(最小生成树果题)
题目链接:http://poj.org/problem?id=1258
Description
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
Output
Sample Input
4 0 4 9 21 4 0 8 17 9 8 0 16 21 17 16 0
Sample Output
28
Source
代码如下:
#include <stdio.h> #include <string.h> #define INF 0x3f3f3f3f #define MAXN 517 //创建m二维数组储存图表,low数组记录每2个点间最小权值,visited数组标记某点是否已访问 int m[MAXN][MAXN], low[MAXN], visited[MAXN]; int n; int prim( ) { int i, j; int pos, minn, result=0; memset(visited,0,sizeof(visited)); visited[1] = 1; pos = 1; //从某点开始,分别标记和记录该点 for(i = 1; i <= n; i++) //第一次给low数组赋值 if(i != pos) low[i] = m[pos][i]; else low[i] = 0; for(i = 1; i < n; i++) //再运行n-1次 { minn = INF; //找出最小权值并记录位置 for(j=1; j<=n; j++) { if(visited[j]==0 && minn>low[j]) { minn = low[j]; pos = j; } } result += minn; //最小权值累加 visited[pos] = 1; //标记该点 for(j = 1; j <= n; j++) //更新权值 if(visited[j]==0 && low[j]>m[pos][j]) low[j] = m[pos][j]; } return result; } int main() { int i,j,ans; while(scanf("%d",&n)!=EOF) { memset(m,INF,sizeof(m)); //所有权值初始化为最大 for(i = 1; i <= n; i++) for(j = 1; j <= n; j++) { scanf("%d",&m[i][j]); } ans=prim( ); printf("%d\n",ans); } return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。