POJ 2485 - Highways


问题描述

无。

解题思路

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

思路、解法都和 [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/lyy289065406/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/lyy289065406/POJ-Solving-Reports/doc/程序设计导引及在线实践.pdf)
- [ACM 资料](https://lyy289065406.github.io/articles/tags/ACM/)

文章作者: EXP
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 EXP !
 上一篇
POJ 1584 - A Round Peg in a Ground Hole POJ 1584 - A Round Peg in a Ground Hole
POJ 1584 - A Round Peg in a Ground Hole Time: 1000MS Memory: 10000K 难度: 初级 分类: 多边形算法 问题描述按照顺时针或逆时针方向输入一个n边形的顶点坐标集,先判断这
2011-07-02
下一篇 
POJ 1408 - Fishnet POJ 1408 - Fishnet
POJ 1408 - Fishnet Time: 1000MS Memory: 10000K 难度: 初级 分类: 多边形算法 问题描述一个1X1的正方形,每条边上有n个不同的点(不包括顶点),并给出它们的坐标。现在把对边相对应的点相连
2011-06-28
  目录