SRM 460 Div2 Hard TheCitiesAndRoadsDivTwo

問題

http://apps.topcoder.com/stat?c=problem_statement&pm=10774&rd=14146

グラフが与えられる。これを全域木にするような辺の加え方の集合はいくつあるか。

やりかた

（説明が間違っていそうです。）
practice roomの回答を参考にしました。
全域木とするためにまずはグラフ中にいくつのサブグラフがあるか数える。これはどのノードとどのノードがくっついているか調べればいいのでワーシャルフロイドでできる。その後各サブグラフはいくつのノードを含んでいるかを計算する。これがvectorvに入る。ここで各サブグラフを一つのノードとして考えると、これらのノードが木になるグラフの数はノード数をNとするとN^{N - 2}になる。これをケイリーの公式というらしい。知らなかったよー。で、このノードというのはサブグラフ一つを一つのノードに見立てたものだったのでサブグラフiの実際のノード数[i]をかけてやれば良い。

class TheCitiesAndRoadsDivTwo {
public:
  int find(vector <string> map) {
    int result = 1;
    int N = map.size();
    vector<bool> used(10, false);
    vector<int> v;

    //Warshall-Floyd
    for(int i = 0; i < N; i++)
      for(int j = 0; j < N; j++)
	for(int k = 0; k < N; k++)
	  if(map[i][j] == 'Y' && map[i][k] == 'Y')
	    map[j][k] = 'Y';

    for(int i = 0; i < N; i++){
      if(!used[i]){
	map[i][i] = 'Y';
	int cnt = 0;
	for(int j = 0; j < N; j++){
	  if(map[i][j] == 'Y'){
	    cnt++;
	    used[j] = true;
	  }
	}
	v.push_back(cnt);
      }
    }

    if(v.size() == 1) return 1;
    for(int i = 0; i < (int)v.size() - 2; i++)
      result *= N;
    for(int i = 0; i < (int)v.size(); i++)
      result *= v[i];
    return result;
  }
};

知らなかった。自分の実力ではまだできそうもない。。。