Highways
Time Limit: 1000MS
|
Memory Limit: 65536K
|
Total Submissions: 16037
|
Accepted: 7460
|
题目链接:http://poj.org/problem?id=2485
Description
The island nation of Flatopiais perfectly flat. Unfortunately, Flatopia has no public highways. So thetraffic is difficult in Flatopia. The Flatopian government is aware of thisproblem. They're planning to build some highways so that it will
be possible todrive between any pair of towns without leaving the highway system.
Flatopian towns are numbered from 1 to N. Each highway connects exactly twotowns. All highways follow straight lines. All highways can be used in bothdirections. Highways can freely cross each other, but a driver can only switchbetween highways at a town that
is located at the end of both highways.
The Flatopian government wants to minimize the length of the longest highway tobe built. However, they want to guarantee that every town is highway-reachablefrom every other town.
Input
The first line of input is aninteger T, which tells how many test cases followed.
The first line of each case is an integer N (3 <= N <= 500), which is thenumber of villages. Then come N lines, the i-th of which contains N integers,and the j-th of these N integers is the distance (the distance should be aninteger within [1, 65536]) between
village i and village j. There is an emptyline after each test case.
Output
For each test case, you shouldoutput a line contains an integer, which is the length of the longest road tobe built such that all the villages are connected, and this value is minimum.
Sample Input
1
3
0 990 692
990 0 179
692 179 0
Sample Output
692
Hint
Huge input,scanf isrecommended.
Source
POJ Contest,Author:Mathematica@ZSU
题意:
给你一张图,让你求最小生成树中最大的边
解题思路:
直接用prim算法来求解即可。
代码:
#include <iostream>
#include<cstdio>
#include<cstring>
#define MAX 503
#define VALUE 0xfffff
using namespace std;
int g[MAX][MAX];
char gra[MAX][7];
int minCost[MAX];
int visited[MAX];
int prim(int n)
{
int i;
for(i=0;i<n;i++)
{
visited[i]=0;
minCost[i]=VALUE;
}
minCost[0]=0;
// int res=0;
int max=0;
while(true)
{
int t=-1;
for(i=0;i<n;i++)
{
if(visited[i]==0 && (t==-1 || minCost[i]<minCost[t]))
{
t=i;
}
}
if(t==-1)
break;
visited[t]=1;
if(minCost[t]>max)
{
max=minCost[t];
}
// res+=minCost[t];
for(i=0;i<n;i++)
{
if(minCost[i]>g[i][t] && g[i][t]!=0)
{
minCost[i]=g[i][t];
}
}
}
return max;
}
int main()
{
int ts;
int i,j;
scanf("%d",&ts);
while(ts--)
{
memset(g,0,sizeof(g));
int n;
scanf("%d",&n);
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
scanf("%d",&g[i][j]);
}
}
printf("%d\n",prim(n));
}
return 0;
}
分享到:
相关推荐
poj 2485 Highways 测试数据 解题报告:http://blog.csdn.net/qq7366020/article/details/8615293
北大POJ2485-Highways【Prim】 解题报告+AC代码
2遍dp poj_3613解题报告 poj_3613解题报告
poj题目2775文件子目录源代码,递归经典题目,
poj典型题目解题思路详解 包含源代码和解题时应注意的问题及题目陷阱设计分析
poj 1699的代码和方法说明,个人原创
C_(POJ_1854)(分治).cpp
poj上第1990题目源码,用到了2个树状数组,这题数据结构是关键,想到了题目就很简单了
D_(POJ_1723)(思维)(sort).cpp
Unfortunately, Flatopia has no public highways. So the traffic is difficult in Flatopia. The Flatopian government is aware of this problem. They're planning to build some highways so that it will be ...
原理为:以数链思想,移动数组中的内容 使数组在没有扩充情况下,达成移动的效果 当然,有更简单的,大牛不要笑哦
D_(POJ_1723)(思维)(第k大数).cpp
O(nlogn)凸包问题 poj2187
POJ 3131 双向BFS解立体八数码问题
poj两道题的c++实现。已经测试过可以通过oj
POJ题目及算法,包括动态规划、深搜广搜等算法。含相关注释。
问题:求平面上多个矩形的总面积。 算法:线段树(经典的线段树题目)
这是北大在线测试的第1002题,方便记忆的电话号码的解题例程,题目中有一个列表,记录着许多方便记忆的电话号码。不同的方便记忆的电话号码可能对应相同的标准号码,这个程序的任务就是找到它们
poj 3310 的代码和方法说明,个人原创
http://poj.grids.cn/problem?id=2774 POJ 2774 木棒加工 木材厂有一些原木,现在想把这些木头切割成一些长度相同的小段木头,需要得到的小段的数目是给定了。当然,我们希望得到的小段越长越好,你的任务是计算能够...