PKU 2831 Can We Build This One?
http://poj.org/problem?id=2831
n個の街の間に高速道路を建設したい。
m個の高速道路の建設候補があり、それぞれは街aと街bを双方向に結び建設コストcがかかる。
このとき、出来るだけ少ないコストですべての街を行き来できるように建設したい。
ここで、ある高速道路の建設コストを減らしたときに、それは作られる高速道路に含むことが出来るかを答えろというような問題。
一筋縄じゃひかなそうなものが解けて満足。
まず、最初に与えられた高速道路情報で最小全域木を作成する。
そしたら、全頂点間について、ある頂点からある頂点まで移動するのに通過する辺の最大コストを求める。
各クエリに対して、値下げされたコストが、辺がつないでいる頂点間の辺の最大コストより大きくなければその高速道路を使うことができる。
int cost[1000][1000]; int un[1000]; vector<PI> G[1000]; 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); } pair<int,PI> ed[100000]; pair<int,PI> in[100000]; bool vis[1000]; void bfs(int v){ memset(vis,0,sizeof(vis)); queue<PI> q; q.push(mp(v,0)); while(!q.empty()){ int cv=q.front().F; int cc=q.front().S; q.pop(); if(vis[cv])continue; vis[cv]=true; FOR(it,G[cv]){ if(vis[it->F])continue; cost[v][it->F]=cost[it->F][v]=max(cc,it->S); q.push(mp(it->F,max(cc,it->S))); } } } main(){ int n,m,q; scanf("%d%d%d",&n,&m,&q); rep(i,n)un[i]=i; rep(i,m){ scanf("%d%d%d",&ed[i].S.F,&ed[i].S.S,&ed[i].F); in[i]=ed[i]; } sort(ed,ed+m); rep(i,m){ int a=ed[i].S.F,b=ed[i].S.S; int c=ed[i].F; --a,--b; if(find(a)==find(b))continue; unit(a,b); G[a].pb(mp(b,c)); G[b].pb(mp(a,c)); } rep(i,n)bfs(i); rep(j,q){ int i,x; scanf("%d%d",&i,&x); --i; int a=in[i].S.F-1,b=in[i].S.S-1; puts(cost[a][b]>=x?"Yes":"No"); } }