TopCoder SRM 589 Div1 Easy GooseTattarrattatDiv1

問題

英小文字からなる文字列が与えられる。
文字列に対して、文字x, yを選び、文字列に現れるすべてのxをyに置換することができる。
このときにかかるコストはxが現れている回数である。

この操作を繰り返し行い、文字列を回文になるようにしたい。
かかるコストの最小値はいくつか、求めよ。

制約条件

文字列の長さ≦50

方針

文字列をsとすると、
すべてのiについて、s[i]とs[n-i-1]が一致しなければならない。

aからzまでの26頂点からなるグラフを考える。
s[i]の文字とs[n-i-1]の文字の頂点に辺を張ったグラフを考える。

このグラフに対して、辺のある頂点はすべて一箇所にまとめなければならない。
頂点をまとめるのにかかるコストは頂点の重さ（文字の出現回数）に等しい。
なので、連結成分毎に、一番重い頂点にまとめればいい。

ソースコード

int cnt[26];
bool v[26], e[26][26];
pi rec(int c){
	v[c] = 1;
	pi res(cnt[c], cnt[c]);
	rep(i, 26) if(e[c][i] && !v[i]){
		pi p = rec(i);
		res.second += p.second;
		res.first = max(res.first, p.first);
	}
	return res;
}

class GooseTattarrattatDiv1 {
	public:
	int getmin(string S) {
		int ans = 0;
		memset(v, 0, sizeof(v));
		memset(e, 0, sizeof(e));
		memset(cnt, 0, sizeof(cnt));
		
		rep(i, S.size()){
			cnt[S[i] - 'a']++;
		}
		rep(i, S.size() / 2){
			int j = S.size() - 1 - i;
			e[S[i] - 'a'][S[j] - 'a'] = 1;
			e[S[j] - 'a'][S[i] - 'a'] = 1;
		}
		
		rep(i, 26) if(!v[i]){
			pi p = rec(i);
			ans += p.second - p.first;
		}
		return ans;
	}
};