P3959 宝藏
Description
参与考古挖掘的小明得到了一份藏宝图,藏宝图上标出了 $n$ 个深埋在地下的宝藏屋, 也给出了这 $n$ 个宝藏屋之间可供开发的 $m$ 条道路和它们的长度。
小明决心亲自前往挖掘所有宝藏屋中的宝藏。但是,每个宝藏屋距离地面都很远,也就是说,从地面打通一条到某个宝藏屋的道路是很困难的,而开发宝藏屋之间的道路则相对容易很多。
小明的决心感动了考古挖掘的赞助商,赞助商决定免费赞助他打通一条从地面到某个宝藏屋的通道,通往哪个宝藏屋则由小明来决定。
在此基础上,小明还需要考虑如何开凿宝藏屋之间的道路。已经开凿出的道路可以 任意通行不消耗代价。每开凿出一条新道路,小明就会与考古队一起挖掘出由该条道路所能到达的宝藏屋的宝藏。另外,小明不想开发无用道路,即两个已经被挖掘过的宝藏屋之间的道路无需再开发。
新开发一条道路的代价是 $\mathrm{L} \times \mathrm{K}$。其中 $L$ 代表这条道路的长度,$K$ 代表从赞助商帮你打通的宝藏屋到这条道路起点的宝藏屋所经过的宝藏屋的数量(包括赞助商帮你打通的宝藏屋和这条道路起点的宝藏屋) 。
请你编写程序为小明选定由赞助商打通的宝藏屋和之后开凿的道路,使得工程总代价最小,并输出这个最小值。
Input
第一行两个用空格分离的正整数 $n,m$,代表宝藏屋的个数和道路数。
接下来 $m$ 行,每行三个用空格分离的正整数,分别是由一条道路连接的两个宝藏屋的编号(编号为 $1-n$),和这条道路的长度 $v$。
Output
一个正整数,表示最小的总代价。
Sample #1
Sample Input #1
4 5
1 2 1
1 3 3
1 4 1
2 3 4
3 4 1
Sample Output #1
4
Sample #2
Sample Input #2
4 5
1 2 1
1 3 3
1 4 1
2 3 4
3 4 2
Sample Output #2
5
Hint
【样例解释 $1$】
小明选定让赞助商打通了 $1$ 号宝藏屋。小明开发了道路 $1 \to 2$,挖掘了 $2$ 号宝藏。开发了道路 $1 \to 4$,挖掘了 $4$ 号宝藏。还开发了道路 $4 \to 3$,挖掘了 $3$ 号宝藏。
工程总代价为 $1 \times 1 + 1 \times 1 + 1 \times 2 = 4 $。
【样例解释 $2$】
小明选定让赞助商打通了 $1$ 号宝藏屋。小明开发了道路 $1 \to 2$,挖掘了 $2$ 号宝藏。开发了道路 $1 \to 3$,挖掘了 $3$ 号宝藏。还开发了道路 $1 \to 4$,挖掘了 $4$ 号宝藏。
工程总代价为 $1 \times 1 + 3 \times 1 + 1 \times 1 = 5$。
Constraints
对于 $ 20\%$ 的数据: 保证输入是一棵树,$1 \le n \le 8$,$v \le 5\times 10^3$ 且所有的 $v$ 都相等。
对于 $40\%$ 的数据: $1 \le n \le 8$,$0 \le m \le 10^3$,$v \le 5\times 10^3$ 且所有的 $v$ 都相等。
对于 $ 70\%$ 的数据: $1 \le n \le 8$,$0 \le m \le 10^3$,$v \le 5\times 10^3$。
对于 $ 100\%$ 的数据: $1 \le n \le 12$,$0 \le m \le 10^3$,$v \le 5\times 10^5$。
Solution
对于 $n\le 12$ 的数据规模,我们可以想到 状压DP。
考虑设计 $f_{i,j,k}$ 表示总共选的状态是 $i$,当前这一行的状态是 $j$,上一行的状态是 $k$。
因为我们必须由上一行来开发新的宝藏屋,所以要记录上一行的状态。
但是,这样是明显超时的,时间复杂度为 $O(2^n\cdot2^n\cdot2^n)$
我们可以想一下,如果允许与前面的点连边,最终的最小值和现在的连边方式所能得到的最小值是否相同呢?
因为,如果一个深度为 $i$ 的点连向深度为 $i-2$ 的点,那么这样一定是不好的,因为如果将该点移到深度 $i-1$ 再连向深度为 $i-2$ 的那个点,那么边权不会变,而且该点下面的所有点的深度都会 $-1$,这样边权都会减小 $1$ 倍,肯定更优了!
所以深度为 $i$ 的点如果想值最小,一定是连向上一层的,所以我们即使允许他与再往前的点连,也不会对最小值有影响。
所以,设 $f_{i,j}$ 表示第 $i$ 层,选择的方案为 $j$,此时需枚举 $k$,即当前深度所选的方案($k$ 必须为 $j$ 的子集)。
$f_{i,j}=\min(f_{i,j},f_{i-1,j\oplus k}+cost)$
$cost$ 就是当前这些点加在第 $i$ 层所需的花费。
Code
#include <iostream>
#include <cstring>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int SIZE = 14, SIZE2 = 1 << SIZE, INF = 0x3f3f3f3f3f3f3f3f;
int N, M;
int D[SIZE][SIZE], G[SIZE][SIZE2];
int F[SIZE][SIZE2];
signed main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
cin >> N >> M;
memset(D, 0x3f, sizeof D);
for (int i = 0; i < N; i ++) D[i][i] = 0;
while (M --)
{
int u, v, c;
cin >> u >> v >> c;
u --, v --;
D[u][v] = D[v][u] = min(D[u][v], c);
}
memset(G, 0x3f, sizeof G);
for (int i = 0; i < N; i ++)
for (int j = 0; j < 1 << N; j ++)
for (int k = 0; k < N; k ++)
if (j >> k & 1)
G[i][j] = min(G[i][j], D[i][k]);
memset(F, 0x3f, sizeof F);
for (int i = 0; i < N; i ++) F[0][1 << i] = 0;
for (int i = 1; i < 1 << N; i ++)
for (int j = i - 1 & i; j; j = j - 1 & i)
{
int Left = i ^ j, Cost = 0;
for (int k = 0; k < N; k ++)
if (j >> k & 1)
{
Cost += G[k][Left];
if (Cost >= INF) break;
}
if (Cost >= INF) continue;
for (int k = 1; k < N; k ++)
F[k][i] = min(F[k][i], F[k - 1][Left] + Cost * k);
}
int Result = INF;
for (int i = 0; i < N; i ++)
Result = min(Result, F[i][(1 << N) - 1]);
cout << Result << endl;
return 0;
}