POJ 2485 Highways (水題入門最小生成樹)

Description

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

題目大意

在 1~n 個城鎮之間建設公路，求可以把所有城鎮連接配接起來的最小花費，輸出其中最長的邊的權值。

解題思路

1. Prim算法： Prim算法是選取一個點作為出發點，在其餘點中選取距離該點最近的頂點，與出發點合并為集合，并标記已經添加過的頂點避免重複通路；之後不斷往集合中添加距離現有生成樹最近的點，擴大現有生成樹集合，直至所有的點均被标記，現有生成樹集合不再被更新,退出算法。

2.Kruskal算法：Kruskal算法是先把邊遞增排序，然後由小邊至大邊進行檢索，若加入該點會成環，那麼舍棄；否則現有生成樹存在頂點數 +1，直至頂點數等于圖所有頂點，退出算法。在該算法中，使用并查集來判斷兩點是否屬于同一集合，即是否存在環。

代碼實作

//Prim算法

#include <iostream>
#include<cstdio>
using namespace std;
#define maxv 506
#define INF (1<<26)
int edge[maxv][maxv],n;
void prim()
{
    int mincost[maxv];
    bool flag[maxv];
    for(int i=0;i<n;i++)
    {
        mincost[i]=INF;
        flag[i]=false;
    }
    mincost[0]=true;
    int res=0;
    while(true)
    {
        int v=-1;
        for(int u=0;u<n;u++)
        {
            if(!flag[u]&&(v==-1||mincost[u]<mincost[v]))
                v=u;
        }
        if(v==-1)break;
        flag[v]=true;
        res=max(res,mincost[v]);
        for(int u=0;u<n;u++)
            mincost[u]=min(mincost[u],edge[u][v]);
    }
    printf("%d\n",res);
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                scanf("%d",&edge[i][j]);
        prim();
    }
    return 0;
}

           

//kruskal算法

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define maxn 506
int n;
int pre[maxn];
bool flag[maxn];
struct node
{
    int x,y,l;
} edge[maxn*maxn];
bool cmp(node a,node b)
{
    return a.l<b.l;
}
int find_pre(int x)
{
    int r=x;
    while(pre[r]!=r)
    {
        r=pre[r];
    }
    return r;
}
bool make_union(int a,int b)
{
    int fx=find_pre(a);
    int fy=find_pre(b);
    if(fx!=fy)
    {
        pre[fx]=fy;
        return true;
    }
    return false;
}
int main()
{
    int T,v,len;
    scanf("%d",&T);
    while(T--)
    {
        memset(flag,false,sizeof(flag));
        scanf("%d",&n);
        v=0;
        for(int i=0; i<n; i++)
        {
            pre[i]=i;
            for(int j=0; j<n; j++)
            {
                scanf("%d",&len);
                if(i>j)
                {
                    edge[v].x=i;
                    edge[v].y=j;
                    edge[v].l=len;
                    v++;
                }
            }
        }
        int nowv=0;
        int maxx=0;
        sort(edge,edge+v,cmp);
        for(int i=0; i<v; i++)
        {
            if(make_union(edge[i].x,edge[i].y))
            {
                nowv++;
                if(maxx<edge[i].l)
                    maxx=edge[i].l;
                if(nowv==v-1) break;
            }

        }
        printf("%d\n",maxx);
    }
    return 0;
}