kmjp's blog

競技プログラミング参加記です

AtCoder ARC #057 : D - 全域木

B,Cで時間をかけすぎたけど、もう少し時間があれば解けたかも…。
http://arc057.contest.atcoder.jp/tasks/arc057_d

問題

N頂点の完全グラフを考える。
各辺のコストは1~N*(N-1)/2それぞれの値を取るものが1個ずつある。

そのようなグラフのうち、最小全域木を成す(N-1)辺のコストが小さい順にそれぞれA[i]となるようなものの組み合わせ数を求めよ。

解法

プリム法の要領で考える。
A[i]に含まれるコストの辺は、非連結成分を連結するもので、それ以外は既に連結成分である頂点同士を連結するものである。

以下の状態をメモ化再帰の要領で埋めて行こう。
dp(V:=各連結成分数の配列, C:=次に追加する辺のコスト, L:=連結成分中で追加可能な辺の数) := そのような状態から生成できる題意を満たすグラフの組み合わせ数

うまくメモ化再帰するため、Vは常に昇順ソートして並びだけ異なるものを同一視できるようにしておく。
dp({1をN個からなる配列}, 1 ,0)が求める解となる。

dp(V,C,L)は以下のように求められる。

  • CがN*(N-1)/2を超えるなら、全部の辺を配置し終えたのでdp(V,C,L) = 1
  • CがA中で含まれない場合
    • この辺は連結関係を変化させてはいけないので、L本の中で1本追加する。よってdp(V,C,L) = L * dp(V,C+1, L-1)
  • CがA中で含まれる場合
    • V中の2要素V[x],V[y]を総当たりし、連結させるケースを考える。その場合、追加する辺の組み合わせはV[x]*V[y]通り。またこれによりLは(V[x]*V[y]-1)つ候補が増える。
    • V'(x,y) := VからV[x],V[y]を取り除き(V[x]+V[y])を加えてソートしたもの、とするとdp(V,C,L) += V[x]*V[y]*dp(V'(x,y),C+1,L+V[x]*V[y]-1)
int N;
int A[31];
ll mo=1000000007;
int yes[900];

map<vector<int>, ll> memo[900][900];

ll dfs(vector<int> V,int id,int left) {
	
	if(id>N*(N-1)/2) return 1;
	
	if(memo[id][left].count(V)) return memo[id][left][V];
	ll ret=0;
	
	if(yes[id]) {
		if(V.size()>1) {
			int x,y,z;
			FOR(y,V.size()) FOR(x,y) {
				vector<int> V2;
				FOR(z,V.size()) if(z!=x && z!=y) V2.push_back(V[z]);
				V2.push_back(V[x]+V[y]);
				sort(ALL(V2));
				ret += V[x]*V[y]*dfs(V2,id+1,left+V[x]*V[y]-1);
			}
		}
	}
	else {
		if(left) ret = left * dfs(V,id+1,left-1) % mo;
	}
	
	return memo[id][left][V]=ret%mo;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	if(N==1) return _P("1\n");
	
	FOR(i,N-1) cin>>x, yes[x]=1;
	cout<<dfs(vector<int>(N,1),1,0)<<endl;
}

まとめ

本番クラスカル法の要領でやろうとしたけどうまく行かなかった。