Codeforces #250 Div1 A. The Child and Toy

CF250に参加。Cが難しかったこの回、Bを凡ミスオーバーフローしてしまいオレンジに逆戻り。
http://codeforces.com/contest/438/problem/A

問題

N個のパーツからなるおもちゃがあり、このおもちゃをばらばらにしたい。
各パーツのエネルギーV[i]及び、パーツ同士の連結関係が与えられる。
あるパーツをおもちゃから切り離すには、残されたパーツのうち切り離すパーツと連結されたパーツの総エネルギー分のコストがかかる。

全パーツを切り離すまでの総コストを最小化せよ。

解法

連結された2つのパーツを考えると、後に切り離した方のエネルギーがコストとして加算されることになる。
よって、パーツはエネルギーが大きい順に切り離せばよい。
その結果、各連結関係においてエネルギーの小さい方が最終的なコストに反映される。

int N,M;
int V[2000];

void solve() {
	int f,i,j,k,l,x,y;
	cin>>N>>M;
	FOR(i,N) cin>>V[i];
	int ret=0;
	FOR(i,M) {
		cin>>x>>y;
		ret+=min(V[x-1],V[y-1]);
	}
	cout << ret << endl;
}

まとめ

問題設定は一見ややこしいけど、コードは簡単。