NOIPD2T2 – 宝藏 题解

NOIPD2T2 – 宝藏 题解

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

填坑,史前巨坑。
题意:对于一张图,确定一个点为根,构建一个生成树。求代价最小值。
代价的定义:“树中每一条边的权值与较浅点深度的乘积”之和。
考场上没有想清楚就草草码了一个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;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/107507.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • ALLURE架构整理

    ALLURE架构整理ALLURE1.开始安装1.1.安装命令行1.1.1.Linux1.1.2.MacOSX1.1.3.Windows1.1.4.手动安装2.报告结构2.1.总览页面2.2.类别2.3.测试套2.4.图表2.5.时间刻度2.6.功能2.7.包2.8测试用例页面3.Pytest与Allure3.1.安装3.2.用法示例:3.3.基本报告3.4.支持的Pytest功能XfailskipifFixtures和finalizersParametrization3.5AllureFeatu

  • 汇编语言资料_汇编语言基础知识

    汇编语言资料_汇编语言基础知识
    常见的基本汇编书籍 
    Windows.环境下32位汇编语言程序设计(第2版) 
    http://www.happycampus.cn/docs/957100583237@hc10/27
    5980/ 
    汇编语言编程艺术 
    Intel汇编语言程序设计(第四版) 
    Intel汇编语言程序设计(第五版)范例 
    http://download.csdn.net/source/1523425 
    80×86汇编语言程序

    2022年10月13日
  • 用Protel 99 SE学习原理图的设计及pcb的绘制

    用Protel 99 SE学习原理图的设计及pcb的绘制学习Protel99SE的大致过程:原理图文件(*.Sch)–>网络表文件(*.NET)–>*.PCB 网络表文件:记录封装格式。 (封装是指元件的长宽、大小、位置。封装就是一种标准,用来规定元件制造出的实际大小) Pcb文件:它就是印制电路板的文件 protel软件:https://download.csdn….

  • offsetWidth与offsetLeft

    offsetWidth与offsetLeft1、offsetWidth:为元素的width+元素的padding+边框的宽度如图:2、offsetLeft、offsetTop、offsetRight、offsetBottom以offsetLeft为例进行说明,在不同的浏览器中其值不同,且与父元素的position属性(relative,absolute,fixed)有关。现分以下几种情况说明:(测试所用的浏览…

    2022年10月21日
  • Laravel响应和视图

    Laravel响应和视图

  • pycharm如何全局搜索

    pycharm如何全局搜索目录Ctrl+N按文件名搜索py文件Ctrl+shift+N按文件名搜索所有类型的文件ctrl+shift+f全局字符串搜索ctrl+shift+a双shift搜索Ctrl+N按文件名搜索py文件ctrl+n可以搜索py文件勾选上面这个框可以搜索工程以外的文件Ctrl+shift+N按文件名搜索所有类型的文件Ctrl+shift+N可以搜索…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号