POJ1258 Agri-Net（最小生成树）

浏览数：44 / 时间：2015年06月09日

传送门：题目地址
本题是用的prim算法来求解最小生成树。（prim算法和dijkstra算法很相似）
AC代码如下：（题目中有题目翻译以及详细的注释）
技术分享

/*题意如下：
农场主john当选为镇长，他曾许诺要为所以的农场连上网络。
现在有n个农场（包括他自己的农场），要求任意两个农场之间都能互相连通
为了最小化开支，他决定从他的农场向其它农场架设网线，
请问最小开销是多少呢？*/
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int inf=201314;
int n,cost[111][111],mincost[111];//cost[i][j]表示i到j的权值
//mincost[i]表示当前结点到各个结点的最小权值
bool used[111];//标记点已被使用
void prim()
{
    memset(used,false,sizeof(used));
    //初始化最初的顶点到各个结点的距离都为无限大
    for(int i=0;i<n;i++)mincost[i]=inf;
    for(int i=0; i<n; i++)
        mincost[i]=cost[0][i];//赋值
    used[0]=true;
    int sum=0;
    for(int ii=0; ii<n-1; ii++)
    {
        int mins=inf,pos=0;
        for(int i=0; i<n; i++)
            if(!used[i]&&mins>mincost[i])
                mins=mincost[pos=i];//在没有被使用过的结点中找到与当前顶点权值最小的结点。
        used[pos]=true;
        sum+=mins;//将最小权值加上。
        for(int i=0; i<n; i++)
            if(!used[i])//更新当前顶点到其他结点的最小权值。
                mincost[i]=min(mincost[i],cost[pos][i]);
    }
    cout<<sum<<endl;//输出最小生成树的权值和。
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
                scanf("%d",&cost[i][j]);
        prim();//最小生成树算法
    }
    return 0;
}