AOJ 2390: AYBABTU

これがこれで通るのは知識ゲーだと思う。
と思ったけど前にも木上でシュタイナー木作る問題は見たことがあるような…

(非自明)Greedyです。

#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
vector<pair<int,int> > g[11000];
pair<int,pair<int,int> > edge[11000];
int v[11000];
int UF[11000];
int FIND(int a){
	if(UF[a]<0)return a;
	return UF[a]=FIND(UF[a]);
}
void UNION(int a,int b){
	a=FIND(a);b=FIND(b);if(a==b)return;UF[a]+=UF[b];UF[b]=a;
}
int main(){
	int T=0;
	int a,b,c;
	while(scanf("%d%d%d",&a,&b,&c),a){
		int ret=0;
		for(int i=0;i<a-1;i++){
			int p,q,r;scanf("%d%d%d",&p,&q,&r);
			p--;q--;
			g[p].push_back(make_pair(q,r));
			g[q].push_back(make_pair(p,r));
			edge[i]=make_pair(-r,make_pair(p,q));
			ret+=r;
		}
		std::sort(edge,edge+a-1);
		int rem=b-1-c;
		for(int i=0;i<a;i++)UF[i]=-1;
		for(int i=0;i<a;i++)v[i]=0;
		int fi=99999;
		for(int i=0;i<b;i++){
			int p;scanf("%d",&p);
			p--;v[p]=1;
			fi=min(fi,p);
		}
		for(int i=0;i<a;i++){
			if(v[i])UNION(i,fi);
		}
		for(int i=0;i<a-1;i++){
			if(FIND(edge[i].second.first)!=FIND(edge[i].second.second)){
				UNION(edge[i].second.first,edge[i].second.second);
				ret+=edge[i].first;
			}else if(rem){
				rem--;
				UNION(edge[i].second.first,edge[i].second.second);
				ret+=edge[i].first;
			}
		}
		printf("Case %d: %d\n",++T,ret);
	}
}