POJ 2485 - Highways

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

问题描述

无。

解题思路

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

思路、解法都和 [POJ1789](.//Memory Time
//656K 766MS

#include
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;

}

------


## 相关资料

- [北大 ACM - POJ 试题分类](https://exp-blog.com/algorithm/poj-shi-ti-fen-lei/)
- [北大 POJ 题库（官网在线）](http://poj.org/)
- [北大 POJ 题库（离线版）](https://github.com/EXP-Docs/POJ-Solving-Reports/doc/POJ%E7%A6%BB%E7%BA%BF%E7%89%88%E9%A2%98%E7%9B%AE.chm)
- [POJ封面书《程序设计导引及在线实践》](https://github.com/EXP-Docs/POJ-Solving-Reports/doc/程序设计导引及在线实践.pdf)
- [ACM 资料](https://lyy289065406.github.io/articles/tags/ACM/)