SRM654 Div2 Med / OneEntrance

問題

http://community.topcoder.com/stat?c=problem_statement&pm=13698
真姫の新しい家に家具をN個設置したい。部屋の隣接関係と入り口の部屋の番号が与えられ、部屋の隣接関係は木構造をしている。N個の家具を順番に部屋に設置していくが、家具を設置した部屋はその後通行不可になる。全ての家具を設置できる方法が何通りあるか計算する。

解法

制約が小さいので全探索

class OneEntrance {
	public:
	vector<vector<int> > es;
	bool ok(vector<int>& ord,int s){
		vector<bool>used(ord.size());
		for(int i=0;i<ord.size();i++){
			if(!dfs(s,-1,ord[i],used))return false;
		}
		return true;
	}
	bool dfs(int v,int p,int g,vector<bool>& used){
		if(used[v])return false;
		if(v == g){
			used[v] = true;
			return true;
		}
		bool ret = false;
		for(int i=0;i<es[v].size();i++){
			if(es[v][i] == p)continue;
			ret |= dfs(es[v][i],v,g,used);
		}
		return ret;
	}
	int count(vector<int> a, vector<int> b, int s) {
		es.resize(a.size()+1);
		for(int i=0;i<a.size();i++){
			es[a[i]].push_back(b[i]);
			es[b[i]].push_back(a[i]);
		}
		vector<int>ord(a.size()+1);
		for(int i=0;i<a.size()+1;i++){
			ord[i] = i;
		}

		int cnt = 0;
		do{
			if(ok(ord,s))cnt++;

		}while(next_permutation(ord.begin(),ord.end()));
		return cnt;
	}
};

にこまき！