PKU 2263 Heavy Cargo
http://poj.org/problem?id=2263
無向グラフが与えられる。
あるノードvからuに行くのに、通らなければならないエッジのコストの最小値が最大となるような経路のエッジの最小値を答えろというような問題。
最大全域木を作りながら、vからuまで経路が出来たときに加えた辺のコストが答えになる。
int un[200]; int find(int x){ if(x==un[x])return x; return un[x]=find(un[x]); } void unit(int a,int b){ un[find(a)]=find(b); } map<string,int> s2i; int get(const string &st){ if(s2i.count(st))return s2i[st]; int sz=SZ(s2i); return s2i[st]=sz; } main(){ int n,m; int sc=0; while(cin>>n>>m,n){ printf("Scenario #%d\n",++sc); s2i.clear(); priority_queue<pair<int,PI> >q; rep(i,n)un[i]=i; rep(i,m){ string a,b; int t; cin>>a>>b>>t; q.push(mp(t,mp(get(a),get(b)))); } string a,b; cin>>a>>b; int v(get(a)),u(get(b)); while(!q.empty()){ int cc=q.top().F; int t=q.top().S.F; int f=q.top().S.S; q.pop(); unit(f,t); if(find(v)==find(u)){ cout<<cc<<" tons"<<endl<<endl; break; } } } }