SRM 650 Div1 Medium TheKingsRoadsDiv1

グラフ G が与えられる。G が深さ9以下の完全二分木に3本の余計な辺を追加したグラフであるかを判定する問題である。

色々な解法が考えられるが、根の候補を小さくしてから、それが正しいか判定するという方針で解いた。
根の候補を小さくする部分は、
全点間距離を O(N^2) で前計算し、u からの距離が h 以上の頂点の頂点が無く、 距離が h-1 である頂点が floor(2^(h-3)) 個以上存在する頂点 u を候補とすると、だいたい 1 個くらいに絞ることができる。(未証明)

根を固定したあとは、取り除く辺を全部試せば良い。
完全二分木は、葉以外の頂点は子が2つあるという性質を用いて効率よく全探索できる。深さt と、深さ t の頂点集合と、使用済み頂点集合 (used配列) を状態として持つような dfs を行った。(下記コード参照)
下記コードでは、next_permutation を用いて無駄な計算を行っているが、高々、O(N) * (5!)*(4!)*(3!) 程度で計算できる。

#define N 1030
int d[N][N];
vector<int> g[N];
int n, h;
bool used[N];

class TheKingsRoadsDiv1 {
	public:
	void bfs(int u0){
		int *du = &d[u0][0];
		fill(du, du+N, INF);
		du[u0] = 0;
		queue<int> q;
		q.push(u0);
		while(!q.empty()){
			int u = q.front(); q.pop();
			for(auto v: g[u]){
				if(du[v]>du[u]+1){
					du[v] = du[u]+1;
					q.push(v);
				}
			}
		}
	}
	bool dfs(vector<int> us, int t){
		if(t==h-1) return true;
		for(auto u: us) used[u] = true;
		vector<vector<int>> xs;
		vector<int> vs;
		for(auto u: us){
			vector<int> x;
			for(auto v: g[u]){
				if(used[v]) continue;
				x.pb(v);
			}
			if(x.size()>=6||(x.size()<2)){
				for(auto u: us) used[u] = false;
				return false;
			}
			if(x.size()==2){
				vs.pb(x[0]);
				vs.pb(x[1]);
				continue;
			}
			sort(all(x));
			xs.pb(x);
		}
		int l = xs.size();
		if(l<=0){
			if(vs.size()==(1<<(t+1)) && dfs(vs, t+1)) return true;
			for(auto u: us) used[u] = false;
			return false;
		}

		while(true){
			do{
				vector<int> vs2(vs);
				for(auto x: xs){
					rep(i, 2) vs2.pb(x[i]);
				}
				sort(all(vs2)); UNIQUE(vs2);
				if(vs2.size()!=(1<<(t+1))) continue;
				if(dfs(vs2, t+1)) return true;
			}while(next_permutation(all(xs[l-1])));
			for(int i = l-2; ; i--){
				if(i<0){
					for(auto u: us) used[u] = false;
					return false;
				}
				if(next_permutation(all(xs[i]))){
					for(int j = i+1; j <= l-1; j++) sort(all(xs[j]));
					break;
				}

			}
		}
	}
	string getAnswer(int h_, vector <int> a, vector <int> b) {
		h=h_;
		mset(used, 0);
		n = (1<<h)-1;
		rep(i, n) g[i].clear();
		rep(i, a.size()){
			a[i]--; b[i]--;
			g[a[i]].pb(b[i]);
			g[b[i]].pb(a[i]);
		}
		rep(i, n) bfs(i);
		int lb = 1<<(max(h-3, 0));
		rep(i, n){
			int cnt = 0;
			rep(j, n){
				if(d[i][j]==h-1) cnt++;
				if(d[i][j]>=h) cnt = -INF;
			}
			if(cnt >= lb){
				vector<int> x;
				x.pb(i);
				if(dfs(x, 0)) return "Correct";
			}
		}
		return "Incorrect";
	}
};