[ARC057D]全域木

题意：求有多少个边权为$1\cdots\frac{n(n-1)}2$的完全图的最小生成树的边权为$a_{1\cdots n-1}$

啊啊啊我tm真的是什么都不会啊

考虑kruskal的过程：每次选取跨连通块的最小边，考虑设计相应状态的DP

设$f_{V,c,l}$（$V$是一个可重集）表示（连通块大小组成可重集为$V$，当前考虑到$c$这条边，有$l$条边满足加入后不改变连通性）的方案数，我们要求的是$f_{\{1,\cdots,1\},1,0}$

从小到大考虑$c$，边界是$c\gt\frac{n(n-1)}2$时$f_{?,c,?}=1$

如果$c$不在$a$中，那么它不能跨块，这条边必须从$l$条边里选，于是$f_{V,c,l}=l\cdot f_{V,c+1,l-1}$

如果$c$在$a$中，那么它要跨块，考虑合并$V$中的两个连通块，枚举$x,y\in V$并将它们合并，设$V'=V-\{x\}-\{y\}+\{x+y\}$，用$xy\cdot f_{V',c+1,l+xy-1}$来转移

实现可以用map<vector,int>并记忆化（话说我今天才知道vector可以比较...）

#include<stdio.h>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
const int mod=1000000007;
int mul(int a,int b){return(ll)a*b%mod;}
int n;
map<vint,int>f[450][450];
bool us[450];
int dfs(vint v,int c,int l){
	if(c>n*(n-1)/2)return 1;
	if(f[c][l].count(v))return f[c][l][v];
	int res=0;
	if(us[c]){
		vint v2;
		int i,j,k;
		for(i=1;i<(int)v.size();i++){
			for(j=0;j<i;j++){
				v2.clear();
				for(k=0;k<(int)v.size();k++){
					if(k!=i&&k!=j)v2.push_back(v[k]);
				}
				v2.push_back(v[i]+v[j]);
				sort(v2.begin(),v2.end());
				(res+=mul(v[i]*v[j],dfs(v2,c+1,l+v[i]*v[j]-1)))%=mod;
			}
		}
	}else if(l)
		res=mul(l,dfs(v,c+1,l-1));
	return f[c][l][v]=res;
}
int main(){
	int i,x;
	scanf("%d",&n);
	for(i=1;i<n;i++){
		scanf("%d",&x);
		us[x]=1;
	}
	printf("%d",dfs(vint(n,1),1,0));
}

巴特西

[ARC057D]全域木

最新文章

热门文章