POJ 1258 - Agri-Net


问题描述

无。

解题思路

最小生成树的总权值

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;
}

相关资料


文章作者: EXP
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 EXP !
 上一篇
POJ 1328 - Radar Installation POJ 1328 - Radar Installation
POJ 1328 - Radar Installation Time: 1000MS Memory: 10000K 难度: 初级 分类: 心 问题描述无。 解题思路转化问题,使用贪心算法求解。 AC 源码 Download Link
2011-10-15
下一篇 
POJ 2002 - Squares POJ 2002 - Squares
POJ 2002 - Squares Time: 3500MS Memory: 65536K 难度: 初级 分类: 高效查找法 问题描述有一堆平面散点集,任取四个点,求能组成正方形的不同组合方式有多少。 相同的四个点,不同顺序构成的正方
2011-10-11
  目录