Chlience

【题解】[NOIP2017]宝藏 NOIP瞎搞系列
传送门 >ω< UOJ传送门 >ω< Luogu比较恶心的一个状压 DPSolution刚刚看到这道题基本上是懵逼...
扫描右侧二维码阅读全文
17
2018/10

【题解】[NOIP2017]宝藏 NOIP瞎搞系列

传送门 >ω< UOJ
传送门 >ω< Luogu

比较恶心的一个状压 DP

Solution

刚刚看到这道题基本上是懵逼的
最小生成树 曼哈顿树 dfs

最后确定状压

因为每个点的贡献除了跟边长有关,还跟离根的距离有关,考虑将图按深度分层
$f[i][S]$ 表示现在填完了第 $i$ 层, 填完了状态为 $S$ 的点集

注意:这里 $S$ 是指的 $1 - i$ 层所有点的集合,而不仅仅指第 $i$ 层

现在考虑第 $i + 1$ 层选择 $T$ 的贡献
$T - S$ 中直接连边的最小和 $* i$ 即为贡献
即 $g[S][T]$

转移为 $f[i + 1][S + T] = f[i][S] + g[S][T] * i$

为什么这样是正确的?
难道如果 $T$ 中某点 $t$ 连到一个并不是第 $i$ 层的点 $s$ 怎么办?

那么我们设 $s$ 在第 $i - k$ 层,那么这个贡献 $i * dis[s][t]$ 一定要劣于在 $i - k + 1$ 枚举 $T$ 时加入 $t$ 这个点的贡献 $(i - k) * dis[s][t]$

显然所有的 $S - T$ 情况我们都会枚举到,所以说这个答案只会比原来大,而不会比原来优甚至超过理应的最优解

换而言之,这样转移使得非最优解更加不优,而最优解不变,这样最后就能的到正确的最优解

最后预处理下 $g[S][T]$ 优化下
时间复杂度比较神,应该还能优化

代码

#include <bits/stdc++.h>
using namespace std;
int read() {
    int ans = 0 , flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
int n , m;
const int N = 13 , M = 1010;

int dis[N][N];
int s[N] , t[N] , w[N];
long long f[N][1 << (N - 1)];
long long g[1 << (N - 1)][1 << (N - 1)];

int main() {
    n = read(); m = read();
    memset(dis , 127 / 3 , sizeof(dis));
    for(int i = 1 ; i <= m ; ++ i) {
        int u = read() , v = read() , w = read();
        dis[u][v] = dis[v][u] = min(dis[u][v] , w);
    }
    for(int i = 1 ; i < (1 << n) - 1 ; ++ i) {
        for(int j = 1 ; j <= n ; ++ j)
            if((1 << (j - 1)) & i) s[++s[0]] = j;
            else t[++t[0]] = j;
        memset(w , 127 / 3 , sizeof(w));
        for(int j = 1 ; j <= t[0] ; ++ j) //枚举 t,算转移费用
            for(int k = 1 ; k <= s[0] ; ++ k)
                w[j] = min(w[j] , dis[s[k]][t[j]]);

        int T = 0;
        long long sum = 0;
        for(int j = 1 ; j < (1 << t[0]) ; ++ j) {//枚举 t 子集,算转移费用
            T = 0; sum = 0;
            for(int k = 1 ; k <= t[0] ; ++ k)
                if((1 << (k - 1)) & j) {
                    sum += w[k];
                    T += 1 << (t[k] - 1);
                }
            g[i][T] = sum;
        }
        while(s[0]) s[s[0] --] = 0;
        while(t[0]) t[t[0] --] = 0;
    }

    memset(f , 0x3f , sizeof(f));
    for(int i = 1 ; i <= n ; ++ i) f[1][1 << (i - 1)] = 0;
    for(int x = 1 ; x < n ; ++ x) {
        for(int i = 1 ; i < (1 << n) ; ++ i) {
            for(int j = 1 ; j <= n ; ++ j)
                if((1 << (j - 1)) & i) s[++s[0]] = j;
                else t[++t[0]] = j;
            for(int j = 1 ; j < (1 << n) ; ++ j)
                if(i & j) continue;
                else f[x + 1][i + j] = min(f[x + 1][i + j] , f[x][i] + g[i][j] * x);
            while(s[0]) s[s[0] --] = 0;
            while(t[0]) t[t[0] --] = 0;
        }
    }
    
    long long ans = LLONG_MAX;
    for(int i = 1 ; i <= n ; ++ i)
        ans = min(ans , f[i][(1 << n) - 1]);
    printf("%lld\n" , ans);
    return 0;
}
Last modification:October 17th, 2018 at 08:59 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment