题解 P3959 【宝藏】

tth37 · 2019-06-30 01:08:25 · 题解

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

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

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

状态转移：状态肯定是通过挖通道来转移的。如果将u和v之间挖通，则u所在的连通块和v所在的连通块将会合并。如果以u作为根，u到起点的距离为d，则v到起点的距离为(d+1)。方程如下：

其中：

最终要求的答案即为\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;
}