CF839E Mother of Dragons 做题记录

给定一张 $n$ 个点的边集为 $E$ 的无向图和一个正整数 $K$，你要给每个点分配一个非负实数点权 $s_i$，满足 $\sum s_i=K$ 且 $\sum\limits_{(u,v)\in E}s_u\times s_v$ 最大。输出该式子的最大值（保留 $6$ 位小数）。

$1\le n\le 40$，$1\le K\le 1000$。

首先若 $s_i\not=0$ 的点不组成完全图，则可以找到两个相互没有连边的点 $x,y$，不妨假设 $\sum\limits_{(x,v)\in E} s_v\ge \sum\limits_{(y,v)\in E} s_v$，那么把 $s_y$ 全部给 $s_x$ 肯定不劣。

并且根据数学直觉，点权肯定尽量平均分。

那么这就变成了最大团问题，这是个 NP 问题，但是我们有经典随机化算法：

随机一个加点顺序，若加入当前点后还是团则加入，否则不加入。

这个算法很难卡。

代码如下：

#include <iostream>
#include <cstdio>
#include <ctime>
#include <cstdlib>

using namespace std;

const int S=45,TS=1000000,RS=15;

int n,k;
int a[S][S];
int tot,b[S],c[S];

int main()
{
	srand(time(NULL));
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++) scanf("%d",&a[i][j]);
	}
	for(int i=1;i<=n;i++) b[i]=i;
	int ans=0;
	for(int tt=1;tt<=TS;tt++)
	{
		for(int i=1;i<=RS;i++) swap(b[rand()%n+1],b[rand()%n+1]);
		int tot=0;
		for(int i=1;i<=n;i++)
		{
			bool f=true;
			for(int j=1;j<=tot&&f;j++) f&=a[b[i]][c[j]];
			if(f) c[++tot]=b[i];
		}
		ans=max(ans,tot);
	}
	long double res=k*k/(long double)(ans*ans)*(ans*(ans-1)/2);
	printf("%Lf\n",res);
	return 0;
}