|
|
##[$AcWing$ $529$. 宝藏](https://www.acwing.com/problem/content/531/)
|
|
|
|
|
|
### 一、题目描述
|
|
|
|
|
|
参与考古挖掘的小明得到了一份藏宝图，藏宝图上标出了 $n$ 个深埋在地下的宝藏屋，也给出了这 $n$ 个宝藏屋之间可供开发的 $m$ 条道路和它们的长度。
|
|
|
|
|
|
小明决心亲自前往挖掘所有宝藏屋中的宝藏。
|
|
|
|
|
|
但是，每个宝藏屋距离地面都很远，也就是说，从地面打通一条到某个宝藏屋的道路是很困难的，而开发宝藏屋之间的道路则相对容易很多。
|
|
|
|
|
|
小明的决心感动了考古挖掘的赞助商，**赞助商决定免费赞助他打通一条从地面到某个宝藏屋的通道**，通往哪个宝藏屋则由小明来决定。
|
|
|
|
|
|
在此基础上，**小明还需要考虑如何开凿宝藏屋之间的道路**。
|
|
|
|
|
|
已经开凿出的道路可以任意通行不消耗代价。
|
|
|
|
|
|
每开凿出一条新道路，小明就会与考古队一起挖掘出由该条道路所能到达的宝藏屋的宝藏。
|
|
|
|
|
|
另外，小明不想开发无用道路，即两个已经被挖掘过的宝藏屋之间的道路无需再开发。
|
|
|
|
|
|
新开发一条道路的代价是：
|
|
|
|
|
|
**这条道路的长度 $×$ 从赞助商帮你打通的宝藏屋到这条道路起点的宝藏屋所经过的宝藏屋的数量（包括赞助商帮你打通的宝藏屋和这条道路起点的宝藏屋）。**
|
|
|
|
|
|
请你编写程序为小明选定由赞助商打通的宝藏屋和之后开凿的道路，使得工程总代价最小，并输出这个最小值。
|
|
|
|
|
|
**输入格式**
|
|
|
第一行两个用空格分离的正整数 $n$ 和 $m$，代表宝藏屋的个数和道路数。
|
|
|
|
|
|
接下来 $m$ 行，每行三个用空格分离的正整数，分别是由一条道路连接的两个宝藏屋的编号（编号为 $1∼n$），和这条道路的长度 $v$。
|
|
|
|
|
|
**输出格式**
|
|
|
输出共一行，一个正整数，表示最小的总代价。
|
|
|
|
|
|
**数据范围**
|
|
|
$1≤n≤12$,$0≤m≤1000$,$v≤5∗10^5$
|
|
|
|
|
|
**输入样例**：
|
|
|
```cpp {.line-numbers}
|
|
|
4 5
|
|
|
1 2 1
|
|
|
1 3 3
|
|
|
1 4 1
|
|
|
2 3 4
|
|
|
3 4 1
|
|
|
```
|
|
|
|
|
|
**输出样例**：
|
|
|
```cpp {.line-numbers}
|
|
|
4
|
|
|
```
|
|
|
|
|
|
>**注意**
|
|
|
>本题数据有加强，前二十个测试点为 $NOIP$ 官方数据，后三个测试点为加强数据。
|
|
|
|
|
|
|
|
|
### 二、三种解法
|
|
|
|
|
|
|
|
|
<!-- 让表格居中显示的风格 -->
|
|
|
<style>
|
|
|
.center
|
|
|
{
|
|
|
width: auto;
|
|
|
display: table;
|
|
|
margin-left: auto;
|
|
|
margin-right: auto;
|
|
|
}
|
|
|
</style>
|
|
|
<div class="center">
|
|
|
|
|
|
| 维度/方法 | 状压$DP$ | 暴搜+剪枝 | $A$*寻路+剪枝 |
|
|
|
| --------- | ----------- | ----------------------------------------- | ------------------------------------------------- |
|
|
|
| 运行时长 | $1625$ $ms$ | $660$ $ms$ | <font color='red' size=4><b>$26$ $ms$ </b></font> |
|
|
|
| 思维难度 | 高 | <font color='red' size=4><b>低</b></font> | 中 |
|
|
|
|
|
|
</div>
|
|
|
|
|
|
|
|
|
### 三、贪心+暴搜+剪枝
|
|
|
<center><img src='https://i.loli.net/2019/09/28/qHWf52eMcgVpSrm.png'></center>
|
|
|
|
|
|
首先，小明只会开凿可以使各个宝藏点联通的 **最少条路径**，**所以最后这个图将会是一棵树**，而$dfs$图形化后也是一棵树，所以顺理成章的想到$dfs$。
|
|
|
|
|
|
以此为依据，我们可以 **用深搜一步一步构建树**，每个不同形态的树必有一个总代价，**枚举树的构成形态** 即可枚举不同的总代价，各个 **总代价的最小值** 就是答案。
|
|
|
|
|
|
#### $Q$:如何去一步步构建树呢？
|
|
|
|
|
|
我们可以按 **层** 来讨论
|
|
|
|
|
|
**每层都对所有点，讨论是否把$k$点放在该层**
|
|
|
|
|
|
分析题目后我们会发现，每增加一个点:
|
|
|
|
|
|
**这棵树的分数是： 前面已经得到的分数+该点连接上一层的点的边权值 乘以 该层层数**
|
|
|
|
|
|
所以分数会随着点的加入而线性增长，且增加的分数不与前面层的点的结构有关
|
|
|
|
|
|
这样，我们就可以用 **贪心** 的思想，我们总希望边新加的分数最小，这样总分数才会小，所以对于要讨论的一个点$k$，我们找到它与上层的 **最小距离**，即它与上层点（**无论哪个**）的最小边（如果有），即是它加入这棵树后，与上层连接的点；
|
|
|
|
|
|
而对于这棵树，我们只在乎它的得分多少，并不会在乎每层的详细结构。因为影响树的分数的因素只有：在一步一步构建树的过程中，**新加入的点与上一层的点相连的边的边权，我们可以直接理解成这个点与上一层的距离**
|
|
|
|
|
|
所以，在构建一棵树的时候，我们只需要记录它不断增加的得分，对于其结构，只需要知道每一层有哪些点(用于与下一行进行尝试接边)，顺序如何，而不需要记录具体的点边相连状况。
|
|
|
|
|
|
#### 搜索思路
|
|
|
|
|
|
* 枚举每一层，每层都枚举每个点是否放入该层
|
|
|
|
|
|
* 当所有点都构建进了树中，树的可能形态其一就构建完成
|
|
|
|
|
|
* 枚举每一种可能的树的形态，然后讨论 **得分最小值**
|
|
|
|
|
|
总的来说,搜的是树的每种可能状态,由于每点加分满足不被前态影响,所以我们用枚举每个点的方式一步步构建出树，并在过程中得出这种可能树的得分,最后所有树的形态都列出过，所有可能的总得分也都求过了,求个最小值就$OK$了。
|
|
|
|
|
|
#### $Code$
|
|
|
```cpp {.line-numbers}
|
|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
using namespace std;
|
|
|
|
|
|
const int INF = 0x01010101; // 这个上限有点意思，需要仔细思考
|
|
|
const int N = 15; // 点的个数上限
|
|
|
int g[N][N]; // 记录边，就是地图
|
|
|
int n, m; // n个节点，m条边
|
|
|
vector<int> p[N]; // 第一维：哪一行；第二维：此行第几个是哪个点
|
|
|
bool st[N]; // 每个点是否被用过
|
|
|
int res = INF; // 结果
|
|
|
|
|
|
/*
|
|
|
* u:第u层
|
|
|
* k:正在枚举第几号节点，尝试将这个节点填充到u层中去
|
|
|
* cnt:已经使用了cnt个点
|
|
|
* sum:目前生成树最小价值
|
|
|
*/
|
|
|
void dfs(int u, int k, int cnt, int sum) {
|
|
|
if (sum >= res) return; // 走一半就比最优值大,剪枝
|
|
|
if (p[u - 1].size() == 0) return; // 上一层没有选入点（上层为空），树无法继续构建,递归出口
|
|
|
if (cnt == n) { // 所有点都已经被构建到树中，结果有资格参选最优解
|
|
|
res = sum; // 因为上面有最优剪枝，大的都被提前返回了，到达这里时肯定是更小的值
|
|
|
return;
|
|
|
}
|
|
|
|
|
|
if (k > n) { // 该层所有点都讨论过一遍，继续下一层,回到1号节点处开始
|
|
|
dfs(u + 1, 1, cnt, sum);
|
|
|
return;
|
|
|
}
|
|
|
|
|
|
// 如果u层，k号点被标识为用过了
|
|
|
if (st[k]) { // 该点已用，继续讨论下一个节点
|
|
|
dfs(u, k + 1, cnt, sum);
|
|
|
return;
|
|
|
}
|
|
|
|
|
|
int cost = INF; // 找到该点与上层的最小联系
|
|
|
for (int i = 0; i < p[u - 1].size(); i++) // 若没有联系（即与上层所有点不连通），则mini是INF,会被最优性剪枝减去
|
|
|
cost = min(cost, g[p[u - 1][i]][k]); // 上一行的每个节点，如果与k号节点的边相连，并且，权值最小的话，更新cost
|
|
|
|
|
|
// 找到了上一层到u层，使得k点点亮的最小代价值
|
|
|
// 选用此点（可能1）
|
|
|
st[k] = 1; // 标识k点已使用
|
|
|
p[u].push_back(k);
|
|
|
dfs(u, k + 1, cnt + 1, sum + cost * u);
|
|
|
p[u].pop_back();
|
|
|
st[k] = 0; // 回溯
|
|
|
|
|
|
// 不用此点（可能2）
|
|
|
dfs(u, k + 1, cnt, sum);
|
|
|
}
|
|
|
int main() {
|
|
|
memset(g, 0x3f, sizeof g); // 数组初始化
|
|
|
scanf("%d %d", &n, &m);
|
|
|
|
|
|
while (m--) {
|
|
|
int a, b, c;
|
|
|
scanf("%d %d %d", &a, &b, &c);
|
|
|
g[a][b] = g[b][a] = min(g[a][b], c); // 无向图
|
|
|
}
|
|
|
|
|
|
for (int i = 1; i <= n; i++) { // 每个点都当一次根
|
|
|
st[i] = 1; // i点已用
|
|
|
p[0].push_back(i); // 根是第0层,第1个放的是i
|
|
|
dfs(1, 1, 1, 0); // 从第一层,第一个节点，已经使用了一个节点(根),现在的代价是0
|
|
|
p[0].pop_back(); // 回溯
|
|
|
st[i] = 0; // 回溯
|
|
|
}
|
|
|
cout << res << endl;
|
|
|
return 0;
|
|
|
}
|
|
|
```
|
|
|
|
|
|
### 四、$A*$寻路
|
|
|
|
|
|
#### <font color='red'><b>经验总结</b></font>
|
|
|
$A*$寻路，可以理解为是$dfs$爆搜的优化，是先有$dfs$,在性能达不到要求时，再继续扩展优化之，出现了$A*$寻路，而不是上来就知道本题是$A*$寻路。
|
|
|
|
|
|
此方法是在方法二的基础上，加上一个 **估值函数**，这个估值函数用来预测未来跑完全程是否有机会突破最优的解，如果完全没机会，那么就不用再继续搜索此路径了。
|
|
|
|
|
|
|
|
|
#### 如何设计估值函数?
|
|
|
所谓$A*$寻路，可以理解为是一种剪枝的思想，怎么能快速判断是否可以剪枝是关键。
|
|
|
|
|
|
什么样的能剪枝呢？
|
|
|
就是走到某个状态时，以上帝视角直接看到你走到头是啥样，你小子走到头也还是这个德性,提前放弃吧！
|
|
|
|
|
|
你咋知道我不行呢？办法是这样的:
|
|
|
- 假设所有点，都是通过最小代价接入，预处理出总的最小代价$r$
|
|
|
- 随着构建树的进行，当选择把点$k$放在$u$层上时，就扣除掉它的最小代价值$micost[k]$,即剩余最小代价=$r-micost[k]$
|
|
|
- 当行进到$u$层时，假设$u$层将剩余所有点全部放上，那么最小代价是$u*r$,加上前面已经付出的代价$cost$,大于目前的最优结果$res$,就没有必要继续了，因为全放在现在的层都不可能比目前的结果$res$最优，我们还一定把剩下的点全都放在这一层，还可能继续放在后续的层上，再往后面的层放就更白扯了，因为根据计算公式，那样会成本更高，此时判定你不用再继续了。
|
|
|
|
|
|
一旦估算你不行，人家就不再继续尝试了，这当然会节约时间。
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
using namespace std;
|
|
|
const int N = 15;
|
|
|
const int INF = 0x01010101;
|
|
|
|
|
|
int g[N][N]; // 图的邻接矩阵
|
|
|
int n, m; // n个节点，m条边
|
|
|
vector<int> p[N]; // 第一维：哪一行；第二维：此行第几个是哪个点
|
|
|
bool st[N]; // 每个节点是否已使用
|
|
|
int res = INF; // 代价最小值，预求最小，先设最大
|
|
|
int micost[N]; // 每个点最小的代价,相对前一个贪心+暴搜，这个采用了一个估值函数，用于A*寻路
|
|
|
|
|
|
// 现在第u层，讨论k号节点，总共用了cnt个点，现在这棵树价值sum，剩余点的总最小估值代价
|
|
|
void dfs(int u, int k, int cnt, int sum, int r) {
|
|
|
// 最优性剪枝 ！！！最重要！！！只要现阶段不是最小的了就没有继续的必要了
|
|
|
// 假设本层u把剩余的所有节点全部覆盖，那么最小代价根据定义就是r*u,再加上以前积累的sum，
|
|
|
// 总代价就将是sum+r*u,如果此最小代价仍然高于目前取得的小值，那么，此路径无用
|
|
|
if (sum + r * u >= res) return;
|
|
|
if (p[u - 1].size() == 0) return; // 上一层没有选入点（上层为空），树不可能继续构建，该可能不合法，直接跳过
|
|
|
if (cnt == n) {
|
|
|
res = min(sum, res); // 所有点都已经被构建进树中，更新答案，结束这种可能
|
|
|
return;
|
|
|
}
|
|
|
if (k > n) {
|
|
|
dfs(u + 1, 1, cnt, sum, r); // 该层所有点都讨论过一遍，继续下一层
|
|
|
return;
|
|
|
}
|
|
|
if (st[k]) {
|
|
|
dfs(u, k + 1, cnt, sum, r); // 该点已用，直接讨论下一个点
|
|
|
return;
|
|
|
}
|
|
|
|
|
|
// 选用此点（可能1）
|
|
|
int cost = INF; // 找到该点与上层的最小联系(贪心)
|
|
|
for (int i = 0; i < p[u - 1].size(); i++) // 若与上层所有点不连通，则mini是INF,会被最优性剪枝减去
|
|
|
cost = min(cost, g[p[u - 1][i]][k]);
|
|
|
|
|
|
st[k] = 1; // 能算到这里，该点没用过，用下试试
|
|
|
p[u].push_back(k);
|
|
|
dfs(u, k + 1, cnt + 1, sum + cost * u, r - micost[k]);
|
|
|
p[u].pop_back();
|
|
|
st[k] = 0; // 回溯
|
|
|
|
|
|
// 不用此点（可能2）
|
|
|
dfs(u, k + 1, cnt, sum, r);
|
|
|
}
|
|
|
|
|
|
int main() {
|
|
|
memset(g, 0x3f, sizeof g);
|
|
|
memset(micost, 1, sizeof micost);
|
|
|
|
|
|
scanf("%d %d", &n, &m);
|
|
|
while (m--) {
|
|
|
int a, b, c;
|
|
|
scanf("%d %d %d", &a, &b, &c);
|
|
|
g[a][b] = g[b][a] = min(g[a][b], c); // 无向图双向赋值，只取最小值
|
|
|
// 记录接入a,b的最少代价,用于估值
|
|
|
micost[a] = min(micost[a], c);
|
|
|
micost[b] = min(micost[b], c);
|
|
|
}
|
|
|
|
|
|
// 整体最小估值
|
|
|
int r = 0;
|
|
|
for (int i = 1; i <= n; i++) r += micost[i];
|
|
|
|
|
|
for (int i = 1; i <= n; i++) { // 每个点都当一次根
|
|
|
st[i] = 1; // 点已用
|
|
|
p[0].push_back(i); // 根看做第0层
|
|
|
dfs(1, 1, 1, 0, r - micost[i]); // 从第一层开始搜索,考查第1个节点，目前使用了节点个数为1，总代价为0，最小估值为sum-micost[i]
|
|
|
p[0].pop_back();
|
|
|
st[i] = 0; // 以该点为根的数搜索完毕
|
|
|
}
|
|
|
cout << res << endl;
|
|
|
return 0;
|
|
|
}
|
|
|
```
|
|
|
|
|
|
|
|
|
### 五、状压$DP$
|
|
|
|
|
|
|
|
|
#### 前导知识
|
|
|
#### 1、 $x \& (x-1)$
|
|
|
`x & (x-1)` 表示将 `x` 的二进制表示中最后一个 `1` 变成 `0`，如果 `x` 中没有 `1`，则 `x & (x-1)` 的结果是 `0`。
|
|
|
|
|
|
这个技巧是计算机科学中常用的一个 **技巧**，可以用来判断一个数是否是 `2` 的幂、计算一个数的二进制表示中 `1` 的个数等问题。
|
|
|
|
|
|
**举栗子来说明**：
|
|
|
|
|
|
当 `x` 是奇数时，`x` 的二进制表示的最后一位是 `1`，那么 `x-1` 的二进制表示的最后一位是 `0`，而 `x-1` 的其他位都与 `x` 的二进制表示相同，因此 `x & (x-1)` 的运算结果就是将 `x` 的二进制表示中最后一位的 `1` 变成 `0` 的数。
|
|
|
|
|
|
比如 `x = 7`，它的二进制表示是 `111`，那么 `x-1 = 6` 的二进制表示是 `110`，因此我们有：
|
|
|
$$
|
|
|
\ \ \ 7=111(2) \\
|
|
|
\underline{\& 6=110(2)} \\
|
|
|
\ \ \ 6=110(2)
|
|
|
$$
|
|
|
|
|
|
当 `x` 是偶数时，由于 `x` 的二进制表示中最后一位是`0`，`x-1` 的二进制表示中最后一位就是 `1`，因此 `x & (x-1)` 的运算结果就是将 `x` 最后一个非零位置上的 `1` 变成 `0` 的数。
|
|
|
|
|
|
比如 `x = 8`，它的二进制表示是 `1000`，那么 `x-1 = 7` 的二进制表示是 `0111`，因此我们有：
|
|
|
$$
|
|
|
\ \ \ 8 = 1000(2) \\
|
|
|
\underline{\& 7 = 0111(2)}\\
|
|
|
\ \ \ 0 = 0000(2)
|
|
|
$$
|
|
|
|
|
|
|
|
|
#### 2、获取真子集
|
|
|
|
|
|
$Code$
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
#include <bits/stdc++.h>
|
|
|
using namespace std;
|
|
|
|
|
|
/*
|
|
|
二进制数的子集数量计算
|
|
|
子集指的是在原二进制数中1的选择，假设对应的二进制数中有数字1共n个，那么最少选择1个，最多选择n-1个，请找出所有的这样的二进制数子集。
|
|
|
比如二进制数13=(1101)b，有3个位置存在数字1，
|
|
|
那么：
|
|
|
包含1个1的：1000,0100,0001
|
|
|
包含2个1的：1100,1001,0101
|
|
|
共6个
|
|
|
*/
|
|
|
|
|
|
// 输出十进制对应的二进制数(模板)
|
|
|
void print(int n) {
|
|
|
printf("%2d:", n);
|
|
|
// 输出4个数位的二进制数
|
|
|
for (int i = 3; i >= 0; i--) // 由高到低位
|
|
|
printf("%d", n >> i & 1);
|
|
|
puts("");
|
|
|
}
|
|
|
|
|
|
/*
|
|
|
输出n的所有二进制子集
|
|
|
方法1：逻辑清晰，但性能差
|
|
|
|
|
|
理解一下：
|
|
|
(1) i=n-1:显然，子集不包含自身，也就是最大是比自己小1的才可能是第一个最大子集
|
|
|
(2) for (int i = n - 1; i; i--),从可能的最大子集开始，一个个减少，当然可以遍历到每个可能的子集
|
|
|
(3) if ((i & n) == i) 这个位运算，就是通过数位上数字1的与运算，只有超集与之相与，才能保证得到自身，挺好理解
|
|
|
*/
|
|
|
void sub1(int n) {
|
|
|
for (int i = n - 1; i; i--)
|
|
|
if ((i & n) == i) print(i);
|
|
|
}
|
|
|
|
|
|
/*
|
|
|
方法2：优化
|
|
|
*/
|
|
|
void sub2(int n) {
|
|
|
for (int i = n - 1; i; i = (i - 1) & n)
|
|
|
print(i);
|
|
|
}
|
|
|
|
|
|
int main() {
|
|
|
int st = 13; // 1101
|
|
|
sub1(st);
|
|
|
printf("==================================\n");
|
|
|
sub2(st);
|
|
|
return 0;
|
|
|
}
|
|
|
```
|
|
|
|
|
|
|
|
|
> <font color='red' size=4><b>注：$yxc$说过，要像学习外语一样学习算法，除了理解外，也可以针对某些知识采用背下来的办法。会证明更好，不会证明直接背下来做为结论也是可以的。</b></font>
|
|
|
|
|
|
#### 代码证明
|
|
|
```cpp {.line-numbers}
|
|
|
for (int i = n - 1; i; i = (i - 1) & n)
|
|
|
```
|
|
|
|
|
|
时间复杂度为 $O(2^k)$ 其中 $k$ 为 $i$的二进制中 $1$ 的个数。
|
|
|
首先显然 $j$ 会越来越小 , 且每个 $j$ 都必然是 $i$ 的子集 .
|
|
|
|
|
|
假设$\large i'\ \ \ \ \ \ =\underset{有k个数}{...}1\underset{有l个0}{...}$
|
|
|
所以$\large i'-1=\underset{有k个数}{...}0\underset{有l个1}{...}$
|
|
|
|
|
|
最后$i''=(i'-1)\&n$
|
|
|
此时$i''$相较于$i'$少了第$l+1$位的$1$, 但剩下$l$位是全集，中间显然没有合法的子集，所以此方法成立。
|
|
|
|
|
|
#### $3$. 实现思路
|
|
|
|
|
|
看到数据范围就知道大概是个状压了，考虑一下怎么设计状态。
|
|
|
|
|
|
看懂题意，题目的意思就是**找一棵生成树，使得代价和最小**。
|
|
|
|
|
|
|
|
|
> ① **生成树**:在图论中，生成树是指一张连通无向图的一棵包含所有节点且边数最小的生成树。生成树是图的一种特殊的子图，**它包含了原图的所有节点**，但仅有足以构成一棵树的边。生成树有许多应用，比如最小生成树算法用于解决最小成本连通问题，以及在电力网络设计、通信网络等领域。
|
|
|
> ② 本题的 **最小生成树** 和 **广义的最小生成树** 不同
|
|
|
> 因为在本题中，加入连通块的费用是随当前点到起点的路径线性变化的，这也决定了以前学习过的$Prim$算法无效，需要另想办法。
|
|
|
|
|
|
**考虑在 <font color='red' size=4><b>任意时刻</b></font>，关心已经把哪些点加进生成树，以及生成树的最大树高**。
|
|
|
|
|
|
那么我们就设$f_{S,j}$ 为当前生成树已经包含集合$S$中的点，并且树高是$j$。
|
|
|
|
|
|
那么状态转移方程就出来了：
|
|
|
$$\large f_{S,j} =min\{f_{S_{pre},j−1} +cost\}$$
|
|
|
|
|
|
其中$S_{pre}$是$S$的前序子集，也就是真子集，**通过$S_{pre}$ 通过它可以扩展的边可以形成$S$**,$cost$是这次加边的花费。
|
|
|
|
|
|
怎么判断$S_{pre}$ 在转移中是否合法呢？设$P_s$是$S$能拓展到的边的集合，$P$是**可以预处理出来的** 。
|
|
|
|
|
|
考虑$cost$的计算:
|
|
|
|
|
|
设$s'=S\ xor\ S_0$ ，即$s'$是在$S$中，但不在$S_0$中的元素。
|
|
|
|
|
|
这里$cost$的计算显然是对于每个$s'$中的元素取$S_0$ 中的元素向$S$**连一条最短的边求和后$×i$**。
|
|
|
|
|
|
|
|
|
#### 4、闫氏$DP$分析法
|
|
|
**状态表示-集合**
|
|
|
$f_{i,j}$: 当前生成树的状态是$i$ ($i$ 采用二进制压缩存储)，且树的深度为 $j$ 的方案
|
|
|
|
|
|
**状态表示—属性**
|
|
|
$f_{i,j}:$ 该方案构成的生成树，费用最少$Min$
|
|
|
|
|
|
|
|
|
**状态计算**
|
|
|
$$\large f_{i,j}=min(f_{pre,j−1}+j×cost)$$
|
|
|
|
|
|
**初始状态**： $f_{i,0}(0≤i<n)$
|
|
|
> 这是因为题目中明确说明赞助商可以免费打通任何一个节点作为起始节点
|
|
|
|
|
|
**目标状态**： $f_{1⋯1,n}$
|
|
|
|
|
|
|
|
|
其中，$pre$ 是枚举的所有树 $i$ 的真子集，**$cost$ 则是由 $pre$ 扩展一层后变成 $i$ 所用的所有边的边权之和最小值**
|
|
|
|
|
|
**注意**⚠️：这里枚举 $pre$ 首先必须满足一定能够由 $pre$ 自身的点向外扩散一层后能够变成状态 $i$,**这算是一个简单的状态转移优化**，因为如果所有状态都枚举的话，时间复杂度会退化成爆搜。
|
|
|
|
|
|
**答疑解惑**
|
|
|
可能有人看到该 **$DP$分析** 第一时间会有疑问（至少我有）：
|
|
|
|
|
|
在第 $j−1$ 到第 $j$ 层扩展的时候，有没有可能发生一次 $k−1$ 向 $k$ 层的扩展 (其中 $k<j
|
|
|
$)
|
|
|
|
|
|
就是深层向下扩展时，出现了一个浅层往下延伸一个点的情况
|
|
|
|
|
|
根据我们的 **转移方程**，会把那个浅层扩展的路径数按照当前树的深度来计算，使得该方案费用比实际更大
|
|
|
|
|
|
这种方案是实际存在的，而且也是可能成为本题最优解答案的，但是我们可以不用考虑
|
|
|
|
|
|
为什么？因为该最优解方案是可以映射到我们$DP$方案中的某一个方案上的
|
|
|
|
|
|
我举一个简单的例子：
|
|
|
|
|
|
$$f(0001_b,0)→f(0011_b,1)→f(1111_b,2)$$
|
|
|
|
|
|
|
|
|
其中点 $1$ 是通过 $1$ 层的点 $3$ 延伸到第 $2$ 层的，而点 $2$ 是通过起点 $4$ 延伸到第 $1$ 层的
|
|
|
<center><img src='https://cdn.acwing.com/media/article/image/2021/07/30/55909_a4425024f1-IMG_A9751972D483-1.jpeg'></center>
|
|
|
|
|
|
则该类方案都一一映射到下面这类方案下
|
|
|
$$f(0001_b,0)→f(0111_b,1)→f(1111_b,2)$$
|
|
|
<center><img src='https://cdn.acwing.com/media/article/image/2021/07/30/55909_a8b4254af1-IMG_3B8E9937E813-1.jpeg'></center>
|
|
|
|
|
|
也就证明了该类$DP$方案的最终答案可以是最优解。
|
|
|
|
|
|
|
|
|
|
|
|
> $Tips$
|
|
|
> 为了二进制运用方便，读入点的时候减 $1$，所有点从$0$编号到$n-1$。
|
|
|
|
|
|
**$Code$**
|
|
|
```cpp {.line-numbers}
|
|
|
#include <bits/stdc++.h>
|
|
|
using namespace std;
|
|
|
|
|
|
/*
|
|
|
状压DP的二进制表示法,状态压缩DP有两个性质：
|
|
|
1、它说多大就设置多大，不要再扩大设置，速度会慢。
|
|
|
2、一般状态压缩DP数组下标从0开始
|
|
|
*/
|
|
|
const int N = 12; // 节点个数上限
|
|
|
const int M = 1 << N; // 节点的状态表示 2^N种状态
|
|
|
const int INF = 0x3f3f3f3f; // 正无穷
|
|
|
|
|
|
int g[N][N]; // 邻接矩阵，g[i][j]:i号点和j号点之间的距离
|
|
|
|
|
|
// 记录有效状态转移关系
|
|
|
int p[M]; // p[x]:状态x中的存在(指值为1)每一个数位i，通过g[i][j],可以连接到j1,j2,...等节点，最终可以到达的所有状态为p[x]
|
|
|
// 比如i=00001->0号节点值为1，0号节点与1、3号节点之间有边，那么p[i]=p[00001]=01011
|
|
|
|
|
|
int n, m; // 节点数,边数
|
|
|
/* 递推关系： f[S][j]=min(f[Spre][j-1]+cost)
|
|
|
S：当前状态，Spre是指S的所有前序状态，
|
|
|
也就是Spre通过引入某些合法边(当前状态某个位置有1，同时，由此处的1有相关的边。不是只有一条，是数位为1的所有节点都可以引入合法边)
|
|
|
，可以形成S这个状态。 由于引入边的不同，导致代价不一样，需要求代价的最小值
|
|
|
*/
|
|
|
int f[M][N]; // f[i][j]:所有二进制状态表示为i,且树高为j的生成树的集合，属性:最小代价
|
|
|
vector<int> v[N]; // i这个点，到哪些点有边
|
|
|
|
|
|
int main() {
|
|
|
scanf("%d %d", &n, &m); // 节点数量和边数量
|
|
|
|
|
|
// 1、地图初始化
|
|
|
memset(g, 0x3f, sizeof g); // 全部初始为正无穷,描述:所有节点之间均未连通
|
|
|
for (int i = 0; i < n; i++) g[i][i] = 0; // 每个点到自己的距离为0
|
|
|
|
|
|
// 2、读入边
|
|
|
while (m--) {
|
|
|
int a, b, w;
|
|
|
scanf("%d %d %d", &a, &b, &w); // 起点，终点，权值
|
|
|
a--, b--; // 状态压缩，习惯下标从0开始，题目给的节点号是从1开始的，需要统一处理减1
|
|
|
g[a][b] = g[b][a] = min(g[a][b], w); // 无向图 + 防止重边 + 留最小值
|
|
|
v[a].push_back(b), v[b].push_back(a); // 记录下a可以到达哪些点,其实如果不这么记忆的话，那么就需要枚举每个点对着哪些点，因为数据量小，速度应该也挺快
|
|
|
}
|
|
|
|
|
|
/*
|
|
|
3、预处理有效状态之间的转移关系 i->p[i]
|
|
|
转移办法：标识为1的节点上通过枚举已知边,扩展为新状态p[i]
|
|
|
*/
|
|
|
for (int i = 0; i < 1 << n; i++) // 枚举每个状态
|
|
|
for (int j = 0; j < n; j++) // 枚举状态的每个位置
|
|
|
if (i >> j & 1) { // 如果当前位是1
|
|
|
p[i] |= 1 << j; // 原来的i状态中的1，扩展后还是有的
|
|
|
for (int k = 0; k < v[j].size(); k++) p[i] |= 1 << v[j][k]; // 由j带来的扩展点有v[j].size()个
|
|
|
}
|
|
|
/*
|
|
|
Q:问题：
|
|
|
if (i >> j & 1) {
|
|
|
p[i] |= 1 << j;
|
|
|
for (int k = 0; k < v[j].size(); k++) p[i] |= 1 << v[j][k];
|
|
|
}
|
|
|
可以改写成：
|
|
|
if (i >> j & 1) {
|
|
|
p[i] += 1 << j;
|
|
|
for (int k = 0; k < v[j].size(); k++) p[i] += 1 << v[j][k];
|
|
|
} 吗？它们两个是等价的吗？
|
|
|
|
|
|
答：它们并不是完全等价。
|
|
|
这两个表达式都是将二进制数p[i]的第j位设置为1，但是p[i] |= 1 << j;相比p[i] += 1 << j;更加高效。
|
|
|
这是因为使用位运算符OR(|=)可以避免临时变量和函数调用，并且可以利用位级别的并行性加快操作速度。而加法运算则需要进行进位，速度相对较慢。
|
|
|
此外，p[i] += 1 << j; 如果第j位之前已经是1的话，会导致进位，此时p[i]的值会发生改变，而p[i] |= 1 << j; 不会改变已有的位。
|
|
|
|
|
|
回到上面的代码中，如果我们没有写成 | 运算符，而是采用了+运算符，那么根据业务上的逻辑，p[i]的值可能首先被
|
|
|
for (int k = 0; k < v[j].size(); k++) p[i] += 1 << v[j][k]; 进行填充，
|
|
|
那么 j'=v[j][k],就会提前将对应的数值加到p[i]中去，而下次来到执行 p[i] +=1<<j 时，就会造成重复累加，结果错误。
|
|
|
|
|
|
因此，在二进制位运算时，应尽量使用位运算符。
|
|
|
*/
|
|
|
|
|
|
// 4、动态规划
|
|
|
// 4.1 DP数组初始化
|
|
|
memset(f, 0x3f, sizeof f); // 预求最小，先设最大
|
|
|
for (int i = 0; i < n; i++) f[1 << i][0] = 0; // 赞助商决定免费赞助他打通一条从地面到某个宝藏屋的通道",选择打通哪一条都是一样的，都不要钱，所以在选择每一个节点为起点时，费用都是0
|
|
|
|
|
|
// 4.2 状态转移
|
|
|
for (int i = 0; i < 1 << n; i++) { // 枚举每个状态i
|
|
|
for (int j = i - 1; j; j = (j - 1) & i) { // 枚举i状态的真子集j,只有真子集才有资格进行转移
|
|
|
if ((p[j] & i) == i) { // 如果子状态j可以通过已知边，扩展为可以正好匹配i,才是真正可以转移的有效子状态
|
|
|
int x = i ^ j; // x:j->i增加出来的元素，也就是状态差集,都是j里没有，i里有的数字位1
|
|
|
int cost = 0; // cost记录在状态j到达状态i过程中用到的最小花费
|
|
|
for (int k = 0; k < n; k++) // 枚举x每一个节点k
|
|
|
if (x >> k & 1) { // 找出x中数位是1的节点k
|
|
|
int t = INF; // t表示从j到i使得覆盖掉第k个点需要的最小代价
|
|
|
for (int u = 0; u < n; u++) // 枚举j的每一个数位u
|
|
|
if (j >> u & 1) // 如果此数位是1,有资格引边
|
|
|
t = min(t, g[u][k]); // 如果k点是通过u点连接过去的，那么带来的代价就是g[u][k]
|
|
|
cost += t; // 把x的所有元素都纳入的最小代价和
|
|
|
}
|
|
|
|
|
|
/*
|
|
|
当前状态是i,前序状态是j,它们之间的差集是x, k为枚举x的每一个数字1位，为了点亮k点，最小代价是cost，
|
|
|
整体代价：cost*k(层数越深，挖掘成本系数越大)
|
|
|
迁移方式：加边(数位是1，并且，由此可以引出合法边。不只1条，可是多条。)
|
|
|
|
|
|
理解与感悟：
|
|
|
(1) 先有状态转移方程，再有填充顺序
|
|
|
(2) j->i 需要枚举有效状态转移关系
|
|
|
(3) k-1 -> k 就是层次增加了一层
|
|
|
(4) k∈[1,n) 是因为树根在0层，直线的话，最后一层是n-1
|
|
|
(5) 上面的都好办，关键在于这个 cost,这个东西需要枚举两个转移状态之间的对应关系，结合点与点之间的距离才能计算出来
|
|
|
最小的代价和，最小代价和 乘以 层数，才是真正的整体代价。
|
|
|
*/
|
|
|
for (int k = 1; k < n; k++) f[i][k] = min(f[i][k], f[j][k - 1] + cost * k);
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
|
|
|
// 5、枚举答案, 最小值可能出现在任意一层
|
|
|
int res = INF;
|
|
|
for (int i = 0; i < n; i++)
|
|
|
res = min(res, f[(1 << n) - 1][i]); //(1 << n) - 1表示全选状态，即111111...
|
|
|
|
|
|
// 6、输出结果
|
|
|
cout << res << endl;
|
|
|
return 0;
|
|
|
}
|
|
|
```
|
