poj1258

1．链接地址

https://vjudge.net/problem/POJ-1258#author=fuxianda

2．问题描述

有n个农场，已知这n个农场都互相相通，有一定的距离，现在每个农场需要装光纤，问怎么安装光纤能将所有农场都连通起来，并且要使光纤距离最小，输出安装光纤的总距离 
任意两个村庄之间的距离小于 100,000. 

输入样例

4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0

输出样例

28

3．解题思路

给定一个邻接矩阵，要求求出构建出的最短路长度

可以使用克鲁斯卡尔算法或者prim算法

4．算法实现源代码

#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cstdio>
using namespace std;

const int maxn=100+10;
int map[maxn][maxn];
int lowdis[maxn];
int visit[maxn];

int main()
{
    int n;
    while(~scanf("%d",&n)&&n)
    {
        memset(map,0,sizeof(map));
        memset(lowdis,0,sizeof(lowdis));
        memset(visit,0,sizeof(visit));
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                scanf("%d",&map[i][j]);
            }
        }
        
        for(int i=0;i<n;i++)
        {
            lowdis[i]=map[0][i];
        }
        visit[0]=1;
        
        int min,mindis=0,next;
        for(int i=1;i<n;i++)
        {
            min=1e9;
            for(int j=0;j<n;j++)
            {
                if(!visit[j]&&min>lowdis[j])
                {
                    min=lowdis[j];
                    next=j;
                }
            }
            visit[next]=1;
            mindis+=min;
            for(int j=0;j<n;j++)
            {
                if(!visit[j]&&map[next][j]<lowdis[j])
                {
                    lowdis[j]=map[next][j];
                }
            }
        }
        cout<<mindis<<endl;
    }
}