Rockdu's Blog

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

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

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

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

新开发一条道路的代价是：

这条道路的长度 × 从赞助商帮你打通的宝藏屋到这条道路起点的宝藏屋所经过的宝藏屋的数量（包括赞助商帮你打通的宝藏屋和这条道路起点的宝藏屋）。

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

输入格式

第一行两个用空格分离的正整数 nn 和 mm，代表宝藏屋的个数和道路数。

接下来 mm 行，每行三个用空格分离的正整数，分别是由一条道路连接的两个宝藏屋的编号（编号为 11~nn），和这条道路的长度 vv。

输出格式

输出共一行，一个正整数，表示最小的总代价。

样例一

input

4 5
1 2 1
1 3 3
1 4 1
2 3 4
3 4 1

output

4

explanation

小明选定让赞助商打通了 11 号宝藏屋。小明开发了道路 1→21→2，挖掘了 22 号宝藏。开发了道路 1→41→4，挖掘了 44 号宝藏。还开发了道路 4→34→3，挖掘了 33 号宝藏。工程总代价为：

样例二

input

4 5
1 2 1
1 3 3
1 4 1
2 3 4
3 4 2

output

5

explanation

小明选定让赞助商打通了 11 号宝藏屋。小明开发了道路 1→21→2，挖掘了 22 号宝藏。开发了道路 1→31→3，挖掘了 33 号宝藏。还开发了道路 1→41→4，挖掘了 44 号宝藏。工程总代价为：

样例三

见样例数据下载。

限制与约定

• 对于20%的数据：
  • 保证输入是一棵树，1≤n≤81≤n≤8，v≤5000v≤5000 且所有的 vv 都相等。
• 对于40%的数据：
  • 1≤n≤81≤n≤8，0≤m≤10000≤m≤1000，v≤5000v≤5000 且所有的 vv 都相等。
• 对于70%的数据：
  • 1≤n≤81≤n≤8，0≤m≤10000≤m≤1000，v≤5000v≤5000
• 对于100%的数据：
  • 1≤n≤121≤n≤12，0≤m≤10000≤m≤1000，v≤500000v≤500000

时间限制：1s1s

空间限制：256MB

当年NOIP太菜了，70分暴力都没有，只有40分的prim……

现在看来，自己拿到这个题还是不能保证能A……

这道题应该是NOIP2017最难的题了，个人觉得甚至难过了两天的T3。

目前已知的本题最优秀的计数方法仍然是O(n^3*3^n)的。最优化问题可以做是利用了一些性质。

如果有dalao有更优秀的计数方法请高抬贵手留下联系方式qwq，蒟蒻不胜感激。

首先我们记f[i][mask]表示mask中的点已经选了，现在最深处是第i层的最优解。

转移我们直接从没有选择的点中选择一些接到下一层就可以了。

但是每一个点的所在层都是不一样的啊，难道还要记录一个最外层点吗？

这里就要观察最优化问题的性质了，我们可以把每一个点都当作最外层点。考虑把内层点错当成外层点的不合法扩展，容易发现每一个状态的最优解一定会被一次合法的扩展更新到，并且不合法的扩展一定不是最优解。因此可以直接转移，用二项式定理分析子集枚举的复杂度，为O(n^2*3^n)。

建议把子集枚举给define掉，更有可读性。

#define Subset(i, x) for(register int i = x; i; i = (i - 1) & x)

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#define For(i, a, b) for(register int i = a; i <= b; ++i)
#define Subset(i, x) for(register int i = x; i; i = (i - 1) & x)
using namespace std;
const int maxn = 12;
const int inf = 0x3f3f3f3f;
int dp[maxn + 2][1 << maxn], all;
int trans[1 << maxn][1 << maxn];
int n, m, mp[maxn + 2][maxn + 2], ans, u, v, w;
void Min(int &x, const int &a) {x = min(x, a);}
void pre(int mask) {
    int left = all - mask, mn = inf, sum = 0, flag = 0;
    Subset(i, left) {
        sum = 0, flag = 0;
        for(register int j = 1, p = 1; j <= all; j <<= 1, ++p) {
            if(i & j) {
                mn = inf;
                for(register int k = 1; k <= n; ++k)
                    if(mp[p][k] && (mask & (1 << k - 1))) 
                        mn = min(mp[p][k], mn);
                if(mn == inf) {flag = 1; break;}
                sum += mn;
            }
        }
        if(!flag) trans[mask][mask | i] = sum;
    }
}
int main() {
    scanf("%d%d", &n, &m);
    memset(mp, 0x3f, sizeof(mp));
    memset(dp, 0x3f, sizeof(dp));
    all = (1 << n) - 1, ans = inf;
    for(register int i = 1; i <= m; ++i) {
        scanf("%d%d%d", &u, &v, &w);
        mp[u][v] = mp[v][u] = min(mp[v][u], w);
    }
    for(register int i = 1; i < 1 << n; ++i)
    	pre(i);
    for(register int i = 1; i < 1 << n; i <<= 1)
    	dp[0][i] = 0;
    for(register int i = 1; i <= n; ++i) {
        for(register int j = 1; j < 1 << n; ++j)
        	Subset(k, j) if(trans[k][j])
        		dp[i][j] = min(dp[i][j], dp[i - 1][k] + i * trans[k][j]);
        ans = min(ans, dp[i][all]);
    }
    ans = min(ans, dp[0][all]);
    printf("%d", ans);
    return 0;
}

4 5
1 2 1
1 3 3
1 4 1
2 3 4
3 4 1

4

4 5
1 2 1
1 3 3
1 4 1
2 3 4
3 4 2

5