加载中...

POJ 2485 - Highways

算法

原创

发布日期: 2011-07-01

更新日期: 2024-12-17

文章字数: 361

阅读时长: 1 分

阅读次数:

POJ 2485 - Highways
Time: 1000MS
Memory: 65536K
难度: 初级
分类: 最小生成树算法

问题描述

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

解题思路

题意很简单，就是求最小生成树的最大边。

思路、解法都和 POJ1789 基本一致，只是多了一个判定条件

AC 源码

//Memory Time 
//656K  766MS 

#include<iostream>
using namespace std;

const int inf=65540;      //无限大
int dist[501][501];
int n;         //村落数量

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

    int min_w;
    int point;
    int max_in_min=0;

    int low_dis[501];
    memset(low_dis,inf,sizeof(low_dis));

    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;

            }
        }
        if(max_in_min<min_w)           //寻找最小生成树中的最长路径
            max_in_min = min_w;
        s=point;
        u[s]=true;
        m++;
    }
    return max_in_min;
}

int main(void)
{
    int test;
    cin>>test;
    while(test--)
    {
        /*Input*/

        cin>>n;

        int w;        //两点间边权（临时变量）
        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;
}