洛谷 P3959 宝藏【状压dp】

一开始状态设计错了……

设f[i][s]为当前与根节点联通状况为s，最深深度为i

转移的话枚举当前没有和根联通的点集，预处理出把这些点加进联通块的代价（枚举s中的点和当前点的连边乘以i即可），然后用没联通点的集合b去更新f[i+1][s|b]即可

位运算处理用类似lowbit的东西

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int N=15;

int n,m,a[N][N],lg[5005],f[N][5005],g[5005],b[5005],v[N],p[N],tot,ans;

int main()

{

	scanf("%d%d",&n,&m);

	for(int i=0;i<n;i++)

		lg[1<<i]=i;

	for(int i=0;i<n;i++)

		for(int j=0;j<n;j++)

			a[i][j]=1e6;

	for(int i=1,x,y,z;i<=m;i++)

	{

		scanf("%d%d%d",&x,&y,&z);

		x--,y--;

		a[x][y]=a[y][x]=min(a[x][y],z);

	}

	memset(f,0x3f,sizeof(f));

	for(int i=0;i<n;i++)

		f[0][1<<i]=0;

	for(int i=0;i<n;i++)

		for(int s=0;s<(1<<n);s++)

		{

			tot=0;

			for(int j=0;j<n;j++)

				if(!(s&(1<<j)))

				{

					v[tot]=1e6,p[tot]=1<<j;

					for(int k=s;k;k-=(k&(-k)))

						v[tot]=min(v[tot],a[j][lg[k&(-k)]]*(i+1));

					tot++;

				}

			for(int j=1;j<(1<<tot);j++)

			{

				g[j]=g[j-(j&(-j))]+v[lg[j&(-j)]];

				b[j]=b[j-(j&(-j))]|p[lg[j&(-j)]];

				f[i+1][s|b[j]]=min(f[i+1][s|b[j]],f[i][s]+g[j]);

			}

		}

	ans=1e6;

	for(int i=0;i<n;i++)

		ans=min(ans,f[i][(1<<n)-1]);

	printf("%d\n",ans);

	return 0;

}

巴特西

洛谷 P3959 宝藏【状压dp】

最新文章

热门文章