题解-luogu-p3959宝藏

题目链接

输入一个有$n$个点$m$条边的有权无向图。选定任意节点作为根节点。构造一棵生成树，使得树上所有真实边权的总和最小。真实边权的计算公式：$w(u,v)\times L$，其中$L$为根节点到$u$路径上的节点总数。

$1\le n \le 12,1 \le m \le 1000$

感谢@oy的贡献

这道题做了很长时间，从一开始推出错误的状态转移方程，到埋头优化正确的状态转移，前后花了一个多星期……

本题题解可以保证正确性（当然欢迎Hack），却在速度上略有欠缺。

状态定义：$f[s][u][d]$ $s$表示当前已联通的点集，$u$表示当前点集生成树的树根，$d$表示$u$到起点的距离。（注意：$u$不是起点）

状态转移：状态肯定是通过挖通道来转移的。如果将$u$和$v$之间挖通，则$u$所在的连通块和$v$所在的连通块将会合并。如果以$u$作为根，$u$到起点的距离为$d$，则$v$到起点的距离为$(d+1)$。方程如下：
$$
f[s][u][d]=min\lbrace f[s1][u][d]+f[s2][v][d+1]+w(u,v)*d\rbrace
$$
其中：
$$
s1 \cup s2=s,u\in s1,v\in s2,w(u,v)\not= \inf
$$
最终要求的答案即为$\min_{1\le i \le n}f[(1<<n)-1][i][1]$，采用记忆化搜索实现。

代码如下：

#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;

int N, M;
int w[13][13];
int f[1<<13][13][13];

inline int dp(int s, int u, int d) {
    if (f[s][u][d] != -1) return f[s][u][d];
    if (s == (1 << (u - 1))) return f[s][u][d] = 0;
    int& ans = f[s][u][d] = INF;
    for (register int s1 = s; s1; s1 = (s1 - 1) & s) {
        if (!(s1 & (1 << (u - 1)))) continue;
        for (register int v = 1; v <= N; ++v) {
            if (!(s & (1 << (v - 1)))) continue;
            if (w[u][v] == INF) continue;
            int s2 = s ^ s1;
            ans = min(ans, dp(s1, u, d) + dp(s2, v, d + 1) + w[u][v] * d);
        }
    }
    return ans;
}

int main() {
    memset(w, 0x3f, sizeof(w));
    memset(f, -1, sizeof(f));
    scanf("%d%d", &N, &M);
    for (register int i = 1; i <= M; ++i) {
        int u, v, t;
        scanf("%d%d%d", &u, &v, &t);
        w[u][v] = w[v][u] = min(w[u][v], t);
    }
    int ans = INF;
    for (register int u = 1; u <= N; ++u) {
        ans = min(ans, dp((1 << N) - 1, u, 1));
    }
    printf("%d", ans);
    return 0;
}

# 动态规划, 状态压缩

题解-luogu-p3959宝藏

Comments

一言（ヒトコト）

Recent

Categories

Tag Cloud

Your browser is out-of-date!