PKU 2485-Highways

問題概要

N個の町があり、それぞれを繋ぐ道路を建設するのにかかる費用が与えられる。全ての町が繋がるような最小のコストの木のうち、もっとも高いコストの辺を求めよ

解法

最小全域木をする

実装(C++)

#include <algorithm>
#include <vector>
#include <iostream>
#include <cmath>
#include <queue>
using namespace std;
struct Edge{
        int src,dst,cost;
};
Edge Edges[500*500];
int m;
int n;
int T;
bool operator<(const Edge &a,const Edge &b){
        return a.cost<b.cost;
}
struct UnionFind{
        vector<int> par;
        UnionFind(int n){
                par=vector<int>(n);
                for(int i=0;i<n;i++)par[i]=i;
        }
        int find(int x){
                if(par[x]==x)return x;
                return par[x]=find(par[x]);
        }
        void unite(int x,int y){
                x=find(x);y=find(y);
                if(x==y)return;
                par[x]=y;
        }
        bool same(int x,int y){
                return find(x)==find(y);
        }
};

int main(){
        scanf("%d",&T);
        while(T--){
                m=0;
                scanf("%d",&n);
                int a,b,c;
                for(int i=0;i<n;i++){
                        for(int j=0;j<n;j++){
                                scanf("%d",&c);
                                Edges[m++]=(Edge){i,j,c};
                        }
                }
                stable_sort(Edges,Edges+m);
                UnionFind uf(n);
                int ans=0;
                for(int i=0;i<m;i++){
                        if(uf.same(Edges[i].src,Edges[i].dst))continue;
                        ans=Edges[i].cost;
                        uf.unite(Edges[i].src,Edges[i].dst);
                }
                printf("%d\n",ans);
        }
}