CF1408 - Clusterization Counting

题目大意

给定$n$个点无向带权完全图，求将这些点分组，使得 组内的边边权 都小于 组内点连到组外点的边权

保证边权不同


分析

考虑如何确定合法的分组

从小到大依次加入每一条边，则一个合法的分组一定在某一个时刻满足

1.这个分组是一个极大的连通块

2.这个分组是一个团


dp

考虑类似$\text{Kruskal}$重构树的方法，对于合并的过程转化为树形结构

此时，分组决策只有两种

1.这个点儿子内部分别分组，背包合并

2.如果这个点恰好是合法的分组，那么选择这个点建立新的分组，并且此时儿子必须都是散点

借用树形背包的复杂度分析，$dp$部分复杂度为$O(n^2)$

排序可以桶排

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


const int N=3010,P=998244353;

int n,m,k;
int F[N],S[N],C[N];
int Find(int x){ 
	return F[x]==x?x:F[x]=Find(F[x]); 
}
int dp[N][N/2];
int X[N*N/4],Y[N*N/4];

int main(){
	n=rd();
	rep(i,1,n) F[i]=i,S[i]=1,C[i]=0,dp[i][0]=dp[i][1]=1;
	rep(i,1,n) rep(j,1,n) {
		int x=rd();
		if(i<j) X[x]=i,Y[x]=j;
	}
	rep(i,0,n*n) if(X[i]) {
		int x=Find(X[i]),y=Find(Y[i]);
		if(x==y) {
			if(++C[x]==S[x]*(S[x]-1)/2) dp[x][1]++;
		} else {
			++n;
			rep(a,0,S[x]) rep(b,0,S[y]) if((a>0)==(b>0)) dp[n][a+b]=(dp[n][a+b]+1ll*dp[x][a]*dp[y][b])%P;
			F[x]=F[y]=n,S[n]=S[x]+S[y],C[n]=C[x]+C[y]+1,F[n]=n;
			if(C[n]==S[n]*(S[n]-1)/2) dp[n][1]++;
		}
	}
	rep(i,1,S[n]) printf("%d ",dp[n][i]);
}