Highways - 程序设计

题目描述
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.

输入描述
This problem contains multiple test cases!
The first line of a multiple input is an integer T, then a blank line followed by T input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks.
For each case, the first line 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.

输出描述
The output format consists of T output blocks. There is a blank line between output blocks.
For each 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.

输入样例

输出样例

参考答案
Yizuodi的答案

#include<iostream>
#include<cstring>
using namespace std;
#define inf 0x3f3f3f3f
//0x3f3f3f3f是一个非常神奇的数字，我们用它表示无穷
int E[501][501];//是一个对称的矩阵
int n, length;//城镇的数量和最终公路的长度

void prim(int start)
{
    int visited[501];
    int distance[501];
    memset(visited, 0, sizeof(visited));//全部未访问过
    for (int i = 1; i <= n; i++)
    {
        distance[i] = inf;
    }

    distance[start] = 0;
    for (int i = 1; i <= n; i++)
    {
        int min = inf;
        int u;
        for (int j = 1; j <= n; j++)
        {
            if (visited[j] == 0 && distance[j] < min)
            {
                u = j;
                min = distance[j];
            }
        }
        visited[u] = 1;
        if (length < distance[u]){
            length = distance[u];
        }
        for (int v = 1; v <= n; v++)
        {
            if (visited[v] == 0 && E[u][v] != 0 && E[u][v] < distance[v]){
                distance[v] = E[u][v];
            }
        }
    }
}
 
int main()
{
    int times;//测试样例的数量
    cin >> times;
    while (times --)
    {
        getchar();
        length = 0;
        cin >> n;//城镇的数量为n 
        for(int i = 1;i<=n;i++)
        {
            for (int j = 1; j <= n; j++)
            {
                cin >> E[i][j];
            }
        }
        prim(1);//第一个节点为起点
        cout << length <<endl;
        cout << endl;
    }
}

Yizuodi的缝合答案

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define inf 0x3f3f3f3f
//0x3f3f3f3f是一个非常神奇的数字，我们用它表示无穷
int E[501][501];//邻接矩阵,是一个对称的矩阵
int n, length;//城镇的数量和最长公路的长度
int p[501];

void prim(int start)
{
    int visited[501];
    int distance[501];
    memset(visited, 0, sizeof(visited));//全部未访问过
    for (int i = 1; i <= n; i++)
    {
        distance[i] = inf;
    }
    distance[start] = 0;
    for (int i = 1; i <= n; i++)
    {
        int min = inf;
        int u;
        for (int j = 1; j <= n; j++)
        {
            if (visited[j] == 0 && distance[j] < min)
            {
                u = j;
                min = distance[j];
            }
        }
        visited[u] = 1;
        if (length < distance[u]){
            length = distance[u];
        }
        for (int v = 1; v <= n; v++)
        {
            if (visited[v] == 0 && E[u][v] != 0 && E[u][v] < distance[v]){
                distance[v] = E[u][v];
            }
        }
    }
}

void prim2(int start)
{
    // 定义数据结构lowcost[]，closest[]，s[]
    int lowcost[n+1];
    int closest[n+1];
    bool s[n+1];

    /// 1.初始化lowcost[]，closest[]，s[]
    for (int i = 1; i <= n; i++) {
        if (i != start) {
            lowcost[i] = E[start][i];
            closest[i] = start;
            s[i] = false;
        }
        else
        {
            s[i] = true;
            lowcost[i] = 0;
        }
    }


    // n个节点之间需要找最短路径n-1次
    for (int i = 0; i < n-1; i++) { 
        // 2.找最小
        int tmp = inf, t = start;
        for (int j = 1; j <= n; j++) {
            if (!s[j] && (lowcost[j] < tmp)) {   //!s[j]表示j节点V-U集合中
                t = j;
                tmp = lowcost[j];
            }
        }
        // 找不到，跳出循环
        if (t == start) break;

        // 将t加入集合U
        s[t] = true;  

        // 3.更新
        for (int j = 1; j <= n; j++) {
            if ((!s[j]) && (E[t][j] < lowcost[j])) {
                lowcost[j] = E[t][j];
                closest[j] = t;
            }
        }
    }

    // 4.打印最终结果
    int totalcost = 0;
    cout << "lowcost[]数组：";
    for (int i = 1; i <= n; i++) {
        cout << lowcost[i] << " ";
        totalcost += lowcost[i];
    }
    cout << endl;
    cout << "closest[]数组：";
    for (int i = 1; i <= n; i++) {
        cout << closest[i] << " ";
    }
    cout << endl;
    cout << totalcost;
}


int find(int x)
{
    //查找过程顺带进行了路径压缩
    return (x == p[x]) ? x : (p[x] = find(p[x]));
}
void merge(int x,int y){
    if (find(y) == find(x))
        return;
    p[find(y)] = find(x);
}

void kruskal() {
    int count = 1;//读入n-1条边则停止
    while(count != n){
            int min=inf;
            int x,y;
            for(int i=1;i<=n;++i){
                for(int j=i+1;j<=n;++j){
                    if(find(i) != find(j)&&E[i][j]<min){//找到不会成环的最短边
                        x=i;
                        y=j;
                        min=E[i][j];
                    }
                }
            }
            merge(x,y);//用并查集记录该边的两个端点
            ++count;
            length = min;
    }
}

int main()
{
    int times;//测试样例的数量
    cin >> times;
    while (times --)
    {
        getchar();
        length = 0;
        cin >> n;//城镇的数量为n
        memset(E, inf, sizeof(E)); 
        for(int i = 1;i<=n;i++)
        {
            p[i] = i;//初始化并查集
            for (int j = 1; j <= n; j++)
            {
                cin >> E[i][j];
            }
        }
        kruskal();
        cout << length << endl;
        cout << endl;
    }
}