PKU 3380 Bridges
http://poj.org/problem?id=3380
木が与えられる。k個のエッジでの移動速度を変更することができる。
このとき、全頂点間の移動コストの総和を最小にしたい。
移動速度を変更するk個のエッジを出力しろというような問題。
あるエッジの移動速度を変更したとき、その変更によって総コストがいくら変動するかは、エッジの両端から辿れる頂点数が求められれば求まる。
n本のエッジから辿れる頂点数をO(n)で求めればよい。
ゆとりな感じで書くと、時間がちょっと厳しいようです。
int n,k; ll sh,sc; vector<PI> G[10000]; bool vis[10000]; pair<ll,PI> so[100000]; int sos; int dfs(int v){ if(vis[v]) return 0; vis[v]=true; int ret=1; FOR(it,G[v]){ ll tmp=dfs(it->F); if(tmp) so[sos++]=mp(-tmp*(n-tmp)*it->S*(sc-sh),mp(v,it->F)); ret += tmp; } return ret; } main(){ cin>>n>>k>>sh>>sc; map<PI,int> app; rep(i,n-1){ int b,e,l; scanf("%d%d%d",&b,&e,&l); --b,--e; app[mp(b,e)]=i; app[mp(e,b)]=i; G[b].pb(mp(e,l)); G[e].pb(mp(b,l)); } rep(i,n) if(SZ(G[i])==1){ dfs(i); break; } sort(so,so+sos); rep(i,k) cout<<app[so[i].S]+1<<' '; cout<<endl; }