洛谷P3959 [NOIP2017 提高组] 宝藏题解

题目链接：P3959 [NOIP2017 提高组] 宝藏

题意：

参与考古挖掘的小明得到了一份藏宝图，藏宝图上标出了 \(n\) 个深埋在地下的宝藏屋，也给出了这 \(n\) 个宝藏屋之间可供开发的 \(m\) 条道路和它们的长度。

小明决心亲自前往挖掘所有宝藏屋中的宝藏。但是，每个宝藏屋距离地面都很远，也就是说，从地面打通一条到某个宝藏屋的道路是很困难的，而开发宝藏屋之间的道路则相对容易很多。

小明的决心感动了考古挖掘的赞助商，赞助商决定免费赞助他打通一条从地面到某个宝藏屋的通道，通往哪个宝藏屋则由小明来决定。

在此基础上，小明还需要考虑如何开凿宝藏屋之间的道路。已经开凿出的道路可以任意通行不消耗代价。每开凿出一条新道路，小明就会与考古队一起挖掘出由该条道路所能到达的宝藏屋的宝藏。另外，小明不想开发无用道路，即两个已经被挖掘过的宝藏屋之间的道路无需再开发。

新开发一条道路的代价是 \(\mathrm{L} \times \mathrm{K}\)。其中 \(\mathrm{L}\) 代表这条道路的长度，\(\mathrm{K}\) 代表从赞助商帮你打通的宝藏屋到这条道路起点的宝藏屋所经过的宝藏屋的数量（包括赞助商帮你打通的宝藏屋和这条道路起点的宝藏屋）。

请你编写程序为小明选定由赞助商打通的宝藏屋和之后开凿的道路，使得工程总代价最小，并输出这个最小值。

输入格式：

第一行两个用空格分离的正整数 \(n,m\)，代表宝藏屋的个数和道路数。

接下来 \(m\) 行，每行三个用空格分离的正整数，分别是由一条道路连接的两个宝藏屋的编号（编号为 \(1\sim n\)），和这条道路的长度 \(v\)。

输出格式：

一个正整数，表示最小的总代价。

数据范围：

\(1 \le n \le 12\)，\(0 \le m \le 10^3\)，\(v \le 5\times 10^5\)。

注意到 \(n\) 很小，考虑状压dp。（~~欠了几万年的题了终于写掉了~~）

设 \(f_{i,j,S}\) 表示从起点到节点 \(j(j \not\in S)\) 的距离为 \(i\) ，现在要从 \(j\) 开始建边，连通集合 \(S\) 的最小花费

考虑转移。枚举节点 \(j\) 造出的第一条边 \(j \to k\) 和 \(k\) 要连通到的子集 \(T \subseteq S\) ，则 \[ f_{i,j,S} = \min_{k \in T \subseteq S}\left\{w_{j,k}\times(i+1) + f_{i+1,k,T\setminus \{k\}} + f_{i,j,S\setminus T}\right\} \] 这里枚举 \(k\) 可以先预处理出每个 \(T\) 的 \(\mathsf{lowbit}\) 对应的编号。

最后的答案为 \[ \min_{1 \le i \le n}\left\{f_{0,i,U \setminus \{i\}}\right\} \]

时间复杂度 \(\mathcal{O}(n^33^n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(13))

int n,m;
int d[N][N],sz[1 << N],f[N][N][1 << N],tmp[1 << N];

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    memset(f,0x3f,sizeof(f)); memset(d,0x3f,sizeof(d));
    
    cin >> n >> m;
    for(int i=1,u,v,w; i<=m; i++)
    {
        cin >> u >> v >> w; --u; --v;
        down(d[u][v], w); d[v][u] = d[u][v];
    }
    int mx = (1ll << n) - 1;
    for(int i=1; i<=mx; i++) sz[i] = sz[i & (i - 1)] + 1;
    for(int i=0; i<n; i++) tmp[1 << i] = i;
    for(int i=1; i<=mx; i++) tmp[i] = tmp[i & (-i)];
    for(int i=0; i<n; i++) f[n - 1][i][0] = 0;
    for(int j = n - 2; ~j; --j)
        for(int i = 0; i < n; i++)
        {
            f[j][i][0] = 0;
            for(int S = 1; S <= mx; S++) if((((~S) >> i) & 1) && sz[S] <= n - j - 1)
                for(int T = S; T; T = (T - 1) & S) if(f[j][i][S & (~T)] < f[j][i][S])
                {
                    int l = T;
                    for(int k = tmp[l]; l; k = tmp[l &= (~(1 << k))]) if(d[i][k] < INF)
                            down(f[j][i][S], (j + 1) * d[i][k] + f[j + 1][k][T & (~(1 << k ))] + f[j][i][S & (~T)]);
                }
        }
    int res = INF;
    for(int i=0; i<n; i++) down(res, f[0][i][mx & (~(1 << i))]);
    cout << res << '\n';
    return 0;
}