NOIPD2T2 – 宝藏题解

全栈程序员站长

发布于 2022-07-21 13:20:11

2080

发布于 2022-07-21 13:20:11

文章被收录于专栏：全栈程序员必看全栈程序员必看

大家好，又见面了，我是你们的朋友全栈君。

填坑，史前巨坑。

题意：对于一张图，确定一个点为根，构建一个生成树。求代价最小值。

代价的定义：“树中每一条边的权值与较浅点深度的乘积”之和。

考场上没有想清楚就草草码了一个Prim然后交了，但是因为你代价和深度有关，所以贪心地Prim是错误的。

因为 $N$ 很小，这应当引导我们想到状压。（套路）

答案与深度有关，所以我们可以令 $f[i][S]$ 为最深点深度为 $i$，已选点的集合为 $S$ 时的最小答案。

枚举 $p$ 为 $S$ 的补集的子集，那么

$$f[i][S|p]=min(f[i-1][S]+cost[p])$$

状压可以把集合压成二进制数。（套路 again）

枚举集合补集的子集怎么做？

可以用树状数组中出现的 $lowbit(i)=i\&(-i)$。（小技巧）

如何求 $cost$ 呢？同样用 $lowbit$。

然后我们就可以欢快的转移状态了。特判一下 $N=1$。

代码：

#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#define reg register
#define cmin(_,__) ((_)>(__)?(_)=(__),1:0)
#define cmax(_,__) ((_)<(__)?(_)=(__),1:0)
#define dmin(_,__) ((_)<(__)?(_):(__))
#define dmax(_,__) ((_)>(__)?(_):(__))
#define Abs(_) ((_)>0?(_):-(_))
#define lowbit(_) ((_)&-(_))
using namespace std;
const long long Inf=1ll<<29;
int N,M,tot,pos[15],two[5005],used[5005];
long long f[15][5005],map[15][15],res=Inf,V[15],g[5005];
int main(){
    scanf("%d%d",&N,&M);
    if(N==1){
        puts("0");
        return 0;
    }
    for(reg int i=0;i<N;i++)
        for(reg int j=0;j<N;j++)
            map[i][j]=Inf;
    for(reg int i=1,u,v,w;i<=M;i++){
        scanf("%d%d%d",&u,&v,&w);u--,v--;
        cmin(map[u][v],w);map[v][u]=map[u][v];
    }
    for(reg int i=0;i<N;i++)
        two[1<<i]=i;
    for(reg int i=0;i<=N;i++)
        for(reg int S=0;S<(1<<N);S++)
            f[i][S]=Inf;
    for(reg int i=0;i<N;i++)
        f[0][1<<i]=0;
    for(reg int i=0;i<N;i++){
        for(reg int S=0;S<(1<<N);S++){
            /* 补集 */
            tot=0;
            for(reg int j=0;j<N;j++){
                if(!(S&(1<<j))){
                    V[tot]=Inf;pos[tot]=1<<j;
                    for(reg int x=S;x;x-=lowbit(x))
                        cmin(V[tot],map[j][two[lowbit(x)]]*(i+1));
                    tot++;
                }
            }
            g[0]=used[0]=0;
            for(reg int j=1;j<(1<<tot);j++){
                g[j]=g[j-lowbit(j)]+V[two[lowbit(j)]];
                used[j]=used[j-lowbit(j)]|pos[two[lowbit(j)]];
                cmin(f[i+1][S|used[j]],f[i][S]+g[j]);
            }
        }
    }
    for(reg int i=1;i<=N;i++)
        cmin(res,f[i][(1<<N)-1]);
    printf("%lld\n",res);
    return 0;
}

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/107507.html原文链接：https://javaforall.cn

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022年4月2，如有侵权请联系 cloudcommunity@tencent.com 删除

java