题目描述
参与考古挖掘的小明得到了一份藏宝图,藏宝图上标出了 n个深埋在地下的宝藏屋,
也给出了这 n 个宝藏屋之间可供开发的 m条道路和它们的长度。
小明决心亲自前往挖掘所有宝藏屋中的宝藏。
但是,每个宝藏屋距离地面都很远,也就是说,从地面打通一条到某个宝藏屋的道路是很困难的,而开发宝藏屋之间的道路则相对容易很多。
小明的决心感动了考古挖掘的赞助商,赞助商决定免费赞助他打通一条从地面到某个宝藏屋的通道,通往哪个宝藏屋则由小明来决定。
在此基础上,小明还需要考虑如何开凿宝藏屋之间的道路。
已经开凿出的道路可以任意通行不消耗代价。
每开凿出一条新道路,小明就会与考古队一起挖掘出由该条道路所能到达的宝藏屋的宝藏。
另外,小明不想开发无用道路,即两个已经被挖掘过的宝藏屋之间的道路无需再开发。
新开发一条道路的代价是:
这条道路的长度 ×
从赞助商帮你打通的宝藏屋到这条道路起点的宝藏屋所经过的宝藏屋的数量(包括赞助商帮你打通的宝藏屋和这条道路起点的宝藏屋)。
请你编写程序为小明选定由赞助商打通的宝藏屋和之后开凿的道路,使得工程总代价最小,并输出这个最小值。
输入格式
第一行两个用空格分离的正整数 n 和 m,代表宝藏屋的个数和道路数。
接下来 m 行,每行三个用空格分离的正整数,分别是由一条道路连接的两个宝藏屋的编号(编号为 1∼n),和这条道路的长度 v。
输出格式
输出共一行,一个正整数,表示最小的总代价。
数据范围
1≤n≤12
,
0≤m≤1000
,
v≤5∗105
输入样例:
4 5
1 2 1
1 3 3
1 4 1
2 3 4
3 4 1
输出样例:
4
注意
本题数据有加强,前二十个测试点为 NOIP 官方数据,后三个测试点为加强数据。
算法1
Y总代码注释版本
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 12,M=1<<12,INF=0x3f3f3f3f;
int n,m;
int d[N][N];
int f[M][N],g[M]; //f[x][y]表示状态x中的点组成y层的最小开销
int main(){
scanf("%d%d",&n,&m);
memset(d,0x3f,sizeof d);
//d[x][y] 记录 x y之间的距离 自己同自己的距离为0
for(int i = 0; i < n;i++) d[i][i] = 0;
while(m--){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
a--;b--;
//点序号减1 方便计算
//使用min 比较防止重边
d[a][b]=d[b][a] = min(d[a][b],c);
}
for(int i= 1;i<1<<n;i++){
for(int j= 0;j<n;j++){
if( (i>>j) & 1){
//i状态包含j这个点
for(int k = 0;k <n;k++){
//状态i中有j这个点 j可以到达k
//那么 g[i]记录添加k这个可以达到的点记录
//由于自己点达到自己点距离不是INF是0
//所以g[i]的记录 肯定包含i状态中各个点
if(d[j][k] != INF){
g[i] |= 1<<k;
}
}
}
}
}
memset(f,0x3f,sizeof f);
for(int i= 0;i < n;i++) f[1<<i][0] = 0;
for(int i =1;i<1<<n;i++){
for(int j = (i-1)&i;j;j=(j-1)&i){
if( (g[j] & i) == i){
//j是i的子集, 如果j能一步连上的点和j 包含状态i所有点
//那么就行尝试 状态i 划分为 remain 和j 两部分
int remain = i^j;
int cost = 0;
for(int k = 0;k <n;k++){
//remain状态包含点k
if(remain >>k & 1){
int t = INF;
for(int u = 0;u < n; u++){
//remain中的k点 向j集合中的点 最短路径t
//就是这一次新增加的路径
if(j>>u&1){
t = min(t,d[k][u]);
}
}
cost += t;
}
}
//remain所有点都向j中添加了最短路径
//更新 i个点组合k层的树的最小开销
// 本次循环中i固定,k层可能是1到n-1层
for(int k = 1;k<n;k++){
f[i][k] = min(f[i][k],f[j][k-1]+cost*k);
}
}
}
}
int res = INF;
for(int i= 0;i <n;i++) res = min(res,f[(1<<n) -1][i]);
printf("%d\n",res);
return 0;
}
视频题解空间