首页 > 其他 > 详细

【CF839E】Mother of Dragons 折半状压

时间:2018-01-14 15:44:53      阅读:17      评论:0      收藏:0      [点我收藏+]

标签:子图   font   ()   sof   mic   一个   一半   最大化   ddl   

【CF839E】Mother of Dragons

题意:给你一张n个点,m条边的无向图。你有k点能量,你可以把能量分配到任意一些点上,每个点分到的能量可以是一个非负实数。定义总能量为:对于所有边<a,b>,a的能量*b的能量 的和。让你最大化总能量。

$n\le 40,k\le 1000$

题解:容易发现,最后的分配方案一定是给一个大小为cnt的完全子图中的每个点都分配$k\over cnt$点能量。

那么本题就变成了一般图最大团问题,可以用随机化搞定,这里给出一种meet in the middle算法。

对于前一半的点,用状压预处理出f[S]表示S中的最大团是什么。对于后一半的点,我们可以枚举其中的所有最大团,然后把与这些点都相邻的前一半的点拿出来,用前一半点的f值+后一半点的团大小更新答案即可。

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long ll;
int n,m,n1,n2;
double k;
const int N=(1<<20)+4;
ll v[50];
int f1[N],Log[N],g[N],f2[N],cnt[N];
int main()
{
	scanf("%d%lf",&n,&k);
	int i,j,a;
	for(i=0;i<n;i++)	for(j=0;j<n;j++)
	{
		scanf("%d",&a);
		if(a)	v[i]|=1ll<<j,v[j]|=1ll<<i;
	}
	n1=n/2,n2=n-n/2;
	for(i=0;i<n2;i++)	Log[1<<i]=i;
	for(i=1;i<(1<<n1);i++)
	{
		a=Log[i&-i];
		f1[i]=max(f1[i^(1<<a)],f1[i&v[a]]+1);
	}
	m=f1[(1<<n1)-1];
	g[0]=1,f2[0]=(1<<n1)-1;
	for(i=1;i<(1<<n2);i++)
	{
		a=Log[i&-i];
		f2[i]=f2[i^(1<<a)]&v[a+n1],cnt[i]=cnt[i^(1<<a)]+1;
		if(g[i^(1<<a)]&&(((v[a+n1]>>n1)&i)==(i^(1<<a))))	g[i]=1,m=max(m,f1[f2[i]]+cnt[i]);
	}
	printf("%.10f",k*k*(m-1.0)/m/2.0);
	return 0;
}

【CF839E】Mother of Dragons 折半状压

标签:子图   font   ()   sof   mic   一个   一半   最大化   ddl   

原文:https://www.cnblogs.com/CQzhangyu/p/8283333.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号