P3959 宝藏

题目描述

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

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

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

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

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

\(\mathrm{L} \times \mathrm{K}\)

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

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

输入输出格式

输入格式：

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

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

输出格式：

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

数据规模与约定

对于 \(20\%\) 的数据：保证输入是一棵树， \(1 \le n \le 8\)， \(v \le 5000\) 且所有的 \(v\) 都相等。

对于 \(40\%\) 的数据： \(1 \le n \le 8\) ， \(0 \le m \le 1000\) ， \(v \le 5000\) 且所有的 \(v\) 都相等。

对于 \(70\%\) 的数据： \(1 \le n \le 8\)， \(0 \le m \le 1000\)， \(v \le 5000\)

对于 \(100\%\) 的数据： \(1 \le n \le 12\)，\(0 \le m \le 1000\) ， \(v \le 500000\)

首先，这个题暴力性价比超级高哎

70分pts

#include <cstdio>

#include <cstring>

int min(int x,int y){return x<y?x:y;}

const int N=15;

const int inf=0x3f3f3f3f;

int g[N][N],n,m;

void init()

{

    scanf("%d%d",&n,&m);

    memset(g,0x3f,sizeof(g));

    for(int u,v,w,i=1;i<=m;i++)

    {

        scanf("%d%d%d",&u,&v,&w);

        g[u][v]=min(g[u][v],w);

        g[v][u]=g[u][v];

    }

}

int cho[N],dep[N],ans=inf;

void dfs(int cnt,int cost)

{

    if(cost>=ans) return;

    if(cnt==n) {ans=cost;return;}

    for(int i=1;i<=n;i++)

        if(!cho[i])

        {

            cho[i]=1;

            for(int j=1;j<=n;j++)

                if(cho[j]&&g[i][j]!=inf)

                {

                    dep[i]=dep[j]+1;

                    dfs(cnt+1,cost+dep[j]*g[i][j]);

                }

            cho[i]=0;

        }

}

int main()

{

    init();

    for(int i=1;i<=n;i++)

    {

        dep[i]=1,cho[i]=1;

        dfs(1,0);

        cho[i]=0;

    }

    printf("%d\n",ans);

    return 0;

}

在此基础上，爬山退火甚至剪枝都可以艹过去了，不过我们稍微讨论一下正解。

首先我们得至少按照层数来做，因为它和代价相关。

一个比较好搞出来的想法就是\(dp_{S,d}\)代表已经选中子树\(S\)且其的深度为\(d\)的时候的最小代价。

但是我们发现转移的时候我们需要把点接在最后一层，我们是不是一个搞一个存储最后一层点集的东西呢？？

不行，这样的复杂度还不如直接暴力。

我们强行接点好吗，哪怕接在了不是最后一层的点上，根据题意我们认为道路长度不为负，我们的答案只会大不会小。这样就足够了，因为所有的状态都会被找到，所以非最优的局部不会错过最优解。

尝试列出转移方程

\(dp_{S,d}=min(dp_{las,d-1}+(d-1)\times cost_{las,S})\)

直接遍历两个集合显然不行，我们可以尝试枚举一个S，然后DFS它的子集。而实际上，遍历子集有更方便的写法

对于费用数组\(cost[i][j]\)，我们先求出某个集合对单个点连接的费用（涉及决策），然后更新集合对集合的费用。注意同样要枚举子集。

还要注意，正无穷的费用不能参与更新，否则会爆int

Code:

#include <cstdio>

#include <cstring>

const int inf=0x3f3f3f3f;

const int N=12;

int min(int x,int y){return x<y?x:y;}

int g[N+1][N+1],dp[1<<N][N+1],cost[1<<N][1<<N],c[1<<N][13],n,m,ans=inf;

int main()

{

    scanf("%d%d",&n,&m);

    memset(g,0x3f,sizeof(g));

    for(int u,v,w,i=1;i<=m;i++)

    {

        scanf("%d%d%d",&u,&v,&w);

        g[u][v]=min(g[u][v],w);

        g[v][u]=g[u][v];

    }

    memset(c,0x3f,sizeof(c));

    memset(cost,0x3f,sizeof(cost));

    for(int s=1;s<1<<n;s++)

        for(int i=1;i<=n;i++)

        {

            int mi=inf;

            for(int j=0;j<n;j++)

                if((s>>j)&1)

                    mi=min(mi,g[j+1][i]);

            c[s][i]=mi;

        }

    for(int t=1;t<1<<n;t++)

        for(int s=t-1&t;s;s=s-1&t)

        {

            cost[s][t]=0;

            int k=t-s;

            for(int j=0;j<n;j++)

                if((k>>j)&1)

                {

                    if(c[s][j+1]==inf) {cost[s][t]=inf;break;}

                    cost[s][t]+=c[s][j+1];

                }

        }

    memset(dp,0x3f,sizeof(dp));

    for(int i=0;i<n;i++)

        dp[1<<i][1]=0;

    ans=min(ans,dp[(1<<n)-1][1]);

    for(int d=2;d<=n;d++)

    {

        for(int sta=0;sta<1<<n;sta++)

            for(int las=sta-1&sta;las;las=las-1&sta)

                if(dp[las][d-1]!=inf&&cost[las][sta]!=inf)

                    dp[sta][d]=min(dp[sta][d],dp[las][d-1]+(d-1)*cost[las][sta]);

        ans=min(ans,dp[(1<<n)-1][d]);

    }

    printf("%d\n",ans);

    return 0;

}

2018.8.4

巴特西

洛谷 P3959 宝藏解题报告

P3959 宝藏

题目描述

输入输出格式

输入格式：

输出格式：

数据规模与约定

\(dp_{S,d}=min(dp_{las,d-1}+(d-1)\times cost_{las,S})\)

最新文章

热门文章

巴特西

洛谷 P3959 宝藏 解题报告

P3959 宝藏

题目描述

输入输出格式

输入格式：

输出格式：

数据规模与约定

\(dp_{S,d}=min(dp_{las,d-1}+(d-1)\times cost_{las,S})\)

最新文章

热门文章

洛谷 P3959 宝藏解题报告