首页 > 代码库 > Highways

Highways

2024-11-24 04:52:02   202人阅读

题目：

The island nation of Flatopia is perfectly flat. 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 possible to drive between any pair of towns without leaving the highway system. 

Flatopian towns are numbered from 1 to N. Each highway connects exactly two towns. All highways follow straight lines. All highways can be used in both directions. Highways can freely cross each other, but a driver can only switch between 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 to be built. However, they want to guarantee that every town is highway-reachable from every other town.

Input

The first line of input is an integer T, which tells how many test cases followed. 
The first line of each case is an integer N (3 <= N <= 500), which is the number 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 an integer within [1, 65536]) between village i and village j. There is an empty line after each test case.

Output

For each test case, you should output a line contains an integer, which is the length of the longest road to be 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 is recommended.
 
题意：

平视的岛国是完全平的。不幸的是，平视城没有公共高速公路。所以在平视的情况下交通是很困难的。平坦的政府意识到了这个问题。他们计划修建一些高速公路，以便在不离开高速公路系统的情况下，在任何两个城镇之间驾驶。

平坦的城镇从1到n，每条高速公路都连接着两个城镇。所有的高速公路都是笔直的。所有的高速公路都可以在两个方向上使用。高速公路可以自由交叉，但是司机只能在高速公路的尽头的高速公路之间切换。

平坦的政府希望将最长的公路长度降到最低。然而，他们想要保证每个城镇都能从其他城镇中到达。

输入

输入的第一行是一个整数T，它告诉我们有多少个测试用例。

每一种情况的第一行是整数N(3小于=N小于=500)，这是村庄的数量。然后是N行，第i行包含N个整数，而这些N个整数的j是距离(距离应该是1，65536)在村庄i和j之间的距离，在每个测试用例之后都有一个空行。

输出

对于每个测试用例，您应该输出一条包含一个整数的行，这是要构建的最长的路的长度，这样所有的村庄都连接在一起，并且这个值是最小的。

 

分析：

就是求连接所有城镇的最短路径中最长的那条路；

例子中的连接所有城镇最短路是692+179；

两条路中最长的石692，所以输出692；

 

AC代码：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int n;
const int MAX=1000000;
const int N=505;
int dis[N][N];
int sum[N];
int lowcost[N];
void prim()
{
    int mini,k,s=0;
    for (int i=0;i<n;i++)
        lowcost[i]=dis[0][i];
    for (int i=1;i<n;i++)
    {
        mini=MAX;
        for (int j=0;j<n;j++)
        {
            if (lowcost[j]&&lowcost[j]<mini)
            {
                mini=lowcost[j];;
                k=j;
            }
        }
        sum[s++]=lowcost[k];
        lowcost[k]=0;
        for (int j=0;j<n;j++)
        {
            if (lowcost[j]&&dis[k][j]<lowcost[j])
                lowcost[j]=dis[k][j];
        }
    }
    sort(sum,sum+s);
   printf("%d\n",sum[s-1]);
}
int main()
{
    int t;
    cin>>t;
    while (t--)
    {
        cin>>n;
        for (int i=0;i<n;i++)
            for (int j=0;j<n;j++)
           scanf("%d",&dis[i][j]);
            prim();
    }
    return 0;
}

 

Highways


联系
我们