洛谷P3959：https://www.luogu.org/problemnew/show/P3959
前言
NOIP2017时还很弱（现在也很弱
看出来是DP 但是并不会状压DP
现在看来思路并不复杂 只是存状态有点难想到
思路
因为n最大为12
所以可以想到是状压
因为n<=12 所以可以用邻接矩阵存下图
枚举每个点作为起点开始DFS
注意每次DFS的初始化和赋值问题即可
代码
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define INF 1e9+7
int n,m,ans=
INF;
int f[
8000],h[
15],dis[
15],map[
15][
15];
//dis为题目中的k 即经过了几个宝藏
bool vis[
15][
15];
void dfs(
int s)
{
for(
int i=
1;i<=n;i++
)
{
if(s&(
1<<(i-
1)))
//寻找已经挖通的宝藏
for(
int j=
1;j<=n;j++)
//枚举下一个宝藏
{
if(!(s&(
1<<(j-
1)))&&vis[i][j]&&f[
1<<(j-
1)|s]>f[s]+dis[i]*
map[i][j])
{//如果没有挖过j 且i与j之间有路径 且有一个更优解
int k=dis[j];
//记录原dis方便后面回溯
dis[j]=dis[i]+
1;
//记录新的dis
f[
1<<(j-
1)|s]=f[s]+dis[i]*map[i][j];
//更新更优解
dfs(s|
1<<(j-
1));
dis[j]=k;
//回溯
}
}
}
}
int main()
{
cin>>n>>
m;
memset(map,INF,sizeof(map));
//矩阵赋值最大值
for(
int i=
1;i<=m;i++
)
{
int x,y,z;
cin>>x>>y>>
z;
if(z<map[x][y])
//取最小的一条路
{
map[x][y]=
z;
map[y][x]=
z;
vis[x][y]=
1;
//判断是否存在路径
vis[y][x]=
1;
}
}
for(
int i=
1;i<=n;i++)
//枚举每个点为起点
{
memset(dis,INF,sizeof(dis));
//初始化
memset(f,INF,
sizeof(f));
dis[i]=
1;
//起点经过的点有1个
f[
1<<(i-
1)]=
0;
//当前状态的最小值
dfs(
1<<(i-
1));
//搜索
ans=min(ans,f[(
1<<n)-
1]);
//状态满的时候取最小值
}
cout<<
ans;
}
转载于:https://www.cnblogs.com/BrokenString/p/9822417.html
相关资源：JAVA上百实例源码以及开源项目
