题目描述
参与考古挖掘的小明得到了一份藏宝图,藏宝图上标出了 (n) 个深埋在地下的宝藏屋, 也给出了这 (n) 个宝藏屋之间可供开发的 (m) 条道路和它们的长度。
小明决心亲自前往挖掘所有宝藏屋中的宝藏。但是,每个宝藏屋距离地面都很远, 也就是说,从地面打通一条到某个宝藏屋的道路是很困难的,而开发宝藏屋之间的道路 则相对容易很多。
小明的决心感动了考古挖掘的赞助商,赞助商决定免费赞助他打通一条从地面到某 个宝藏屋的通道,通往哪个宝藏屋则由小明来决定。
在此基础上,小明还需要考虑如何开凿宝藏屋之间的道路。已经开凿出的道路可以 任意通行不消耗代价。每开凿出一条新道路,小明就会与考古队一起挖掘出由该条道路 所能到达的宝藏屋的宝藏。另外,小明不想开发无用道路,即两个已经被挖掘过的宝藏 屋之间的道路无需再开发。
新开发一条道路的代价是:
(L)代表这条道路的长度,(K)代表从赞助商帮你打通的宝藏屋到这条道路起点的宝藏屋所经过的 宝藏屋的数量(包括赞助商帮你打通的宝藏屋和这条道路起点的宝藏屋) 。
请你编写程序为小明选定由赞助商打通的宝藏屋和之后开凿的道路,使得工程总代 价最小,并输出这个最小值。
输入输出格式
输入格式
第一行两个用空格分离的正整数 (n),(m),代表宝藏屋的个数和道路数。
接下来 (m) 行,每行三个用空格分离的正整数,分别是由一条道路连接的两个宝藏 屋的编号(编号为 (1sim n)),和这条道路的长度 (v)。
输出格式
一个正整数,表示最小的总代价。
数据范围
对于 (20\%)的数据: 保证输入是一棵树,(1 le n le 8),(v le 500)且所有的 (v) 都相等。
对于 (40\%)的数据: (1 le n le 8),(0 le m le 1000),(v le 5000)且所有的 (v) 都相等。
对于 (70\%)的数据: (1 le n le 8) ,(0 le m le 1000),(v le 5000)。
对于 (100\%)的数据:(1 le n le 12), (0 le m le 1000),(v le 500000)。
题解
看题第一眼,Prime,但是发现Prime是错的,Prime的贪心准则不符合这道题,看一眼数据范围(1 le n le 12),我们可以用状态压缩,(f[i][j])表示当前已探索的点集为i上一层的点集为j,这样的状态转移就十分简单了,但是,如果仅仅是这样,我们是过不了(100\%)的数据的,我们来想办法压一下维,我们考虑一下能否把第二维压去,但是,我们会发现,这样的话,对于在集合(i)中的点,我们就没有办法直接判定它是在那一层中的。所以我们每次转移时还需要枚举上一层的状态。
代码
#include<bits/stdc++.h>
using namespace std;
long long dist[15][15];
struct Data{
long long sum;
int dist[15];
}dp[1 << 13];
long long inf, ans = 0x7ffffffff;
int main()
{
memset(dist, 0x7f, sizeof(dist));
inf = dist[0][0];
int n, m, x, y;
long long w;
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; ++ i)
{
scanf("%d%d%lld", &x, &y, &w);
dist[x][y] = dist[y][x] = min(dist[x][y], w);
}
int U = (1 << n) - 1;
for(int root = 1; root <= n; ++ root)
{
memset(dp, 0x3f, sizeof(dp));
dp[1 << (root - 1)].dist[root] = 1, dp[1 << (root - 1)].sum = 0;
for(int i = 0; i <= U; ++ i)
{
int S = i | (1 << (root - 1));
for(int u = 1; u <= n; ++ u)
if((S & (1 << (u - 1))))
for(int v = 1; v <= n; ++ v)
if((dist[u][v] != inf) && (!(S & (1 << (v - 1)))))
if(dp[S | (1 << (v - 1))].sum > dp[S].sum + dist[u][v] * ((long long)dp[S].dist[u]))
{
dp[S | (1 << (v - 1))] = dp[S];
dp[S | (1 << (v - 1))].sum = dp[S].sum + dist[u][v] * ((long long)dp[S].dist[u]);
dp[S | (1 << (v - 1))].dist[v] = dp[S | (1 << (v - 1))].dist[u] + 1;
}
}
ans = min(ans, dp[U].sum);
}
printf("%lld
", ans);
}