【做题】arc078_f-Mole and Abandoned Mine——状压dp
2024-10-12 20:52:09
题意:给出一个\(n\)个结点的联通无向图,每条边都有边权。令删去一条边的费用为这条边的边权。求最小的费用以删去某些边使得结点\(1\)至结点\(n\)有且只有一条路径。
\(n \leq 15\)
不难想象出,删去边后所得的图形中,在\(1\)到\(n\)的路径上的每一条边都是桥。换言之,每一条边都连接两个边双联通分量。 \(n \leq 15\)的数据范围显然与状压dp有关,于是我们考虑枚举下一个边双联通分量来完成dp转移,以不断铺设从\(1\)到\(n\)的路径。
令dp状态为dp[S,cur],其中\(S\)为当前已被选的点的集合,且\(1\)到\(n\)的路径以铺设到\(cur\)。那么,我们的转移就是铺设下一个结点,或新增一个包含\(cur\)的边双(不包含\(S\)中的其他结点)。这样,如果记两个集合\(S\),\(T\) 之间所有边的和为co[S,T],我们就能得到转移方程:
- \[{\rm{dp}}[S \bigcup \{ u \},u] = {\rm dp}[S,cur] +{\rm co}[\{ u \},S - \{ cur \}]
\] - \[{\rm dp}[S \bigcup T,cur] = {\rm dp} [S,cur] + {\rm co}[T,S - \{ cur \}]
\]
复杂度是\(O(n \times 3^n)\)。
上面的转移是从题解上抄来的(划。它与直接枚举下一个边双和路径上的结点的做法相比,复杂度上更优越。(后者的复杂度是\(O(n^2 \times 3^n)\)。
顺便一提,co所占用的空间是\(O(3^n)\)的,并且在dp时要注意第一条方程中\(u\)和\(cur\)必须相邻。
#include <bits/stdc++.h>
#define lowbit(x) ((x) & (- (x)))
#define rev(x) (((1 << n) - 1) ^ x)
#define R register
using namespace std;
const int N = 15, MAX = 1 << 15, MAX3 = 14348907, INF = 0x3f3f3f3f;
int n,m,su[N+2][MAX],dp[MAX][N + 2],trans[MAX],co[MAX3];
int main() {
int x,y,z;
scanf("%d%d",&n,&m);
for (int i = 1 ; i <= m ; ++ i) {
scanf("%d%d%d",&x,&y,&z);
su[x][1 << y >> 1] += z;
su[y][1 << x >> 1] += z;
}
for (int i = 1 ; i <= n ; ++ i)
for (R int j = 1 ; j < (1 << n) ; ++ j)
su[i][j] = su[i][j - lowbit(j)] + su[i][lowbit(j)];
for (R int i = 1 ; i < (1 << n) ; ++ i) {
for (int j = 1, t = 1 ; j <= n ; ++ j, t *= 3)
if ((i >> j-1)&1) trans[i] += t;
}
for (R int i = 1 ; i < (1 << n) ; ++ i)
for (R int j = rev(i) ; j ; j = (j-1)&rev(i)) {
int t = trans[i] + 2 * trans[j];
for (int k = 1 ; k <= n ; ++ k)
if ((i >> k-1)&1) co[t] += su[k][j];
}
memset(dp,0x3f,sizeof dp);
dp[1][1] = 0;
for (R int i = 1 ; i < (1 << n) ; ++ i) {
for (int j = 1 ; j <= n ; ++ j) if ((i >> j-1)&1) {
if (dp[i][j] == INF) continue;
for (R int k = rev(i) ; k ; k = (k-1)&rev(i)) if (su[j][k] > 0)
dp[i | k][j] = min(dp[i|k][j],dp[i][j]+co[trans[i^(1<<j>>1)]+2*trans[k]]);
if ((i >> n-1)&1) continue;
for (int k = 1 ; k <= n ; ++ k) if (!((i >> k-1)&1)) if (su[k][1<<j>>1] > 0)
dp[i|(1<<k>>1)][k] = min(dp[i|(1<<k>>1)][k],dp[i][j]+su[k][i^(1<<j>>1)]);
}
}
printf("%d\n",dp[(1 << n) - 1][n]);
return 0;
}
小结:在dp转移时把一步拆成两步,是可以减小复杂度的。
最新文章
- Android6.0运行时权限管理
- Scala的下一步
- hbase-architecture
- 教你在Excel里做GA的水平百分比图的详细步骤(图文教程)-成为excel大师(1)
- CVU介绍
- SQL VS NoSQL 如何选择数据库
- 二.CSS的伪类
- UVa 11361 (计数 递推) Investigating Div-Sum Property
- Delimiter must not be alphanumeric or backslash 问题及解决
- Could not roll back JDBC transaction途径
- 。net加密解密相关方法
- 字符串转xml,特殊字符的问题
- 小程序中input设置宽度后宽度还有空间,但是placeholder被遮挡问题
- python编码,赋值和is的区别
- s21day11 python笔记
- python3 items() 与 python2 中iteritems()的区别
- Docker windows下安装并搭建Nodejs的webapp
- hadoop2.x 异常
- 结对作业——随机生成四则运算(Core 第7组)
- What the difference between __weak and __block reference?
热门文章
- java中JDBC连接Oracle数据库
- Rpgmakermv(24 )yep_coreengine
- hdu5064 DLX可重复覆盖+二分
- python pymssql 连接数据库
- HDU 1233	还是畅通工程 (最小生成树 )
- [转载]oracle的常用函数 instr() 和substr()函数
- Navicat连接MySQL8.0亲测有效
- A2W,W2A等的使用
- codeSourcery交叉编译环境
- FileReader 获取图片base64数据流 并 生成图片