PKU 2485 Highways
http://poj.org/problem?id=2485
n個の村があって、村iから村jまでの道の建設にはcijのコストがかかる。
最小全域木を構成するときに最も長い道路の長さはいくらかというような問題。
PKU 2421を一部変えるだけ。
int un[500]; int find(int x){ if(un[x]==x)return x; return un[x]=find(un[x]); } int unit(int a,int b){ un[find(a)]=un[find(b)]=find(a); } main(){ int t; scanf("%d",&t); while(t--){ int n; scanf("%d",&n); priority_queue<pair<int,PI> > Q; rep(i,n){ un[i]=i; rep(j,n){ int c; scanf("%d",&c); Q.push(mp(-c,mp(i,j))); } } int ans=0; while(!Q.empty()){ int c=-Q.top().F,a=Q.top().S.F,b=Q.top().S.S; Q.pop(); if(find(a)==find(b))continue; ans=c; unit(a,b); } cout<<ans<<endl; } }