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); } }