PKU 1861 Network
http://poj.org/problem?id=1861
n個のノードを結ぶ辺が与えられる。
これらの辺から最大の長さの辺が最小になるように全域木を作り、つかった辺などを出力するというような物。
時間そこそこギリギリで通りました。
最小全域木ですね。
int un[1000]; int find(int x){ if(x==un[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 n,m; cin>>n>>m; priority_queue<pair<int,PI> > q; rep(i,n)un[i]=i; rep(i,m){ int a,b,c; cin>>a>>b>>c; q.push(mp(-c,mp(a-1,b-1))); } vector<PI> P; 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); P.pb(mp(a+1,b+1)); } cout<<ans<<endl; cout<<SZ(P)<<endl; rep(i,SZ(P))cout<<P[i].F<<' '<<P[i].S<<endl; }