【AT2657】【LuoguAT2657】Mole and Abandoned Mine
题目链接1: https://www.luogu.org/problemnew/show/AT2657
题目链接2: https://www.luogu.org/jump/atcoder/2657
引言
时隔一月, 我又回来了写题解了.
以后可能颓的时间会变少. 现在文化课好像更重要些, 还是要专心学习吧.
本题是一个状压练手好题.
分析
我再大致翻译描述一下题目, 我一开始因为没看样例就理解错了.
本题给出N点M边的无向图, 然后要割掉其中一些边, 使从1到N只有一条不经过重复顶点的边, 求删掉的边的边权和最小.
重点是这条路径不需要经过所有点
看数据范围, 只可能是状压或者暴力搜索, 然而难度说明只能是状压了.
很容易想到, 求删边边权最少, 相当于求留下边的边权和最大.
然而我没有想到具体怎么求, 搜到了一个大佬的题解, 最终的图还有一个重要性质:
每个点最多只与保留下来的那条路径上的一个点有边相连
所以我们先预处理出所有的联通块中的边权和.
然后进行DP, 二维数组, 第一维为处理了哪些点, 第二维为到达哪个点(当前终点).
有两种转移, 一种是新处理一个点, 一种是将一个联通块与当前终点相连.
我从这道题还学习了一个新的二进制性质.枚举一个数二进制下的所有子集:
1
2
3
4
| int num = 59; // 某个数
for(int i= num; i; i= (i - 1) & num) {
// i 为 num 的一个二进制子集
}
|
比如（0101）的子集为（0101）,（0100）,（0001）,（0000）.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| #include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
int n, m, nn, edge[16][16], tmpx, tmpy, tmpz, sums;
int blocks[1 << 16], len, f[1 << 16][16];
int main() {
cin >> n >> m;
nn= 1 << n;
for(int i= 1; i <= m; i++) {
cin >> tmpx >> tmpy >> tmpz;
sums+= edge[tmpx][tmpy]= edge[tmpy][tmpx]= tmpz;
}
for(int i= 0; i < nn; i++) {
for(int j= 1; j <= n; j++) {
if(!(i & (1 << (j - 1))) && !(blocks[i | (1 << (j - 1))])) {
blocks[i | (1 << (j - 1))]= blocks[i];
for(int k= 1; k <= n; k++)
if((i & (1 << (k - 1)))) blocks[i | (1 << (j - 1))]+= edge[j][k];
}
}
}
memset(f, -1, sizeof(f));
f[1][1]= 0;
for(int i= 0; i < nn; i++) {
for(int j= 1; j <= n; j++) {
if(f[i][j] != -1 && (i & (1 << (j - 1)))) {
for(int k= 1; k <= n; k++)
if(!(i & (1 << (k - 1))) && edge[j][k]) f[i | (1 << (k - 1))][k]= max(f[i | (1 << (k - 1))][k], f[i][j] + edge[j][k]);
tmpx= ((nn - 1) ^ i) | (1 << (j - 1));
for(int k= tmpx; k; k= (k - 1) & tmpx)
if(k & (1 << (j - 1))) f[i | k][j]= max(f[i | k][j], f[i][j] + blocks[k]);
}
}
}
cout << sums - f[nn - 1][n] << endl;
return 0;
}
|
