【解题报告】洛谷P3959 宝藏

原题连接

https://www.luogu.com.cn/problem/P3959

思路

这道题目，本来今天yht老师讲了个大力搜索，什么模拟退火来着，但是最后，还是回归了本源，状态动态规划

首先我们这么想

我们每条路肯定只联通一次，然后我们对于可以钦定一个集合S

用来表示某个点选不选的最小代价

但我们要进行状态转移，我们要从一个点走到另一个点，然后要用某个节点的深度来计算代价

所以我们设置f[x][S][d]f[x][S][d]来表示点x在S中并且深度为d的时候的最小代价

因为是从上一个状态走下来的，所以我们要加上这条边

则状态转移方程为
f[x][1<<(x−1)∣S][d]=min{sum+dis[y]+g[y][x]} f[x][1<<(x-1)|S][d]=min\{sum+dis[y]+g[y][x]\}
其中y和x表示上次的点和这次的点，sum表示这次以前的最小代价

dis数组在dfs的时候顺便处理一下就好了

代码

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#define int long long
using namespace std;
const int maxn=15;
const int INF=1e9;
int n,m,maxx;
int g[maxn][maxn];
int dis[maxn],ans=INF;
int f[maxn][1<<maxn][maxn];
inline void dfs(int s,int sum,int dep)
{
	if(sum>=ans)
	return ;
	if(s==maxx)
	{
		ans=sum;
		return ;
	}
	for(int i=1;i<=n;i++)
	{
		if(!(1<<(i-1)&s))
		continue;
		for(int j=1;j<=n;j++)
		{
			if(!(1<<(j-1)&s)&&g[i][j]<INF)
			{
				if(f[j][1<<(j-1)|s][dep+1]<=sum+dis[i]*g[i][j])
				continue;
				f[j][1<<(j-1)|s][dep+1]=sum+dis[i]*g[i][j];
				dis[j]=dis[i]+1;
				dfs(1<<(j-1)|s,f[j][1<<(j-1)|s][dep+1],dep+1);
			}
		}
	}
}
signed main()
{
	cin>>n>>m;
	maxx=(1<<n)-1;
	memset(g,0x3f3f3f,sizeof(g));
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		cin>>x>>y>>z;
		g[x][y]=g[y][x]=min(g[x][y],z);
	}
	for(int i=1;i<=n;i++)
	{
		memset(dis,0,sizeof(dis));
		memset(f,0x3f3f3f,sizeof(f));
		dis[i]=1;
		dfs(1<<(i-1),0,0);
	}
	cout<<ans<<'\n';
	return 0;
}