加载中...

POJ 1258 - Agri-Net

算法

原创

发布日期: 2011-10-14

更新日期: 2024-12-17

文章字数: 310

阅读时长: 1 分

阅读次数:

POJ 1258 - Agri-Net
Time: 1000MS
Memory: 10000K
难度: 初级
分类: 最小生成树算法

问题描述

详见 http://poj.org/problem?id=1258

解题思路

求最小生成树的总权值。

AC 源码

//Memory Time 
//300K   32MS 

#include<iostream>
using namespace std;

const int inf=100001;      //无限大

int n;   //农场数量
int dist[101][101];

int prim(void)
{
    int s=1;
    int m=1;
    bool u[101]={false};
    u[s]=true;

    int min_w;
    int prim_w=0;
    int point;
    int low_dis[101];

    /*Initial*/

    for(int i=1;i<=n;i++)
        low_dis[i]=inf;

    /*Prim Algorithm*/

    while(true)
    {
        if(m==n)
            break;

        min_w=inf;
        for(int i=2;i<=n;i++)
        {
            if(!u[i] && low_dis[i]>dist[s][i])
                low_dis[i] = dist[s][i];
            if(!u[i] && min_w>low_dis[i])
            {
                min_w = low_dis[i];
                point=i;
            }
        }
        s=point;
        u[s]=true;
        prim_w+=min_w;
        m++;
    }
    return prim_w;
}

int main(void)
{
    while(cin>>n)
    {
        /*Input*/

        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                cin>>dist[i][j];

        /*Prim Algorithm & Output*/

        cout<<prim()<<endl;
    }
    return 0;
}