【NOIP 2017】宝藏考古发现

考古发现,Description

涉足考古挖掘的小明拿到了一份藏宝图,藏宝图上标出了 n
个深埋在地下的宝藏屋, 也提交了那 n 个宝藏屋之间可供开发的 m
条道路和它们的长短。
小明决心亲自前往挖掘独具宝藏屋中的宝藏。但是,每一种宝藏屋距离地面都很远,
也等于说,从本地挖掘一条到有些宝藏屋的征途是很费劲的,而开发宝藏屋之间的征程
则相对不难很多。
小明的决心感动了考古挖掘的赞助商,赞助商决定免费帮忙他打通一条从地面到某些宝藏屋的大路,通往哪个宝藏屋则由小明来控制
在此基础上,小明还亟需考虑什么开凿宝藏屋之间的道路。已经开凿出的征途可以任意通行不消耗代价。每开凿出一条新征程,小明就会与考古队一起挖掘出由该条道路
所能到达的遗产屋的遗产。其它,小明不想付出无用道路,即五个曾经被打通过的能源屋之间的道路无需再付出。
新开发一条道路的代价是:
\[L×K\]
L代表那条道路的长度,K代表从赞助商帮您打通的宝藏屋到那条道路起源的宝藏屋所经过的
宝藏屋的数量(包涵赞助商帮你打通的宝藏屋和那条道路起源的宝藏屋) 。
请您编写程序为小明选定由赞助商打通的宝藏屋和今后开凿的道路,使得工程总代
价最小,并出口那个小小值。

solution

正解:状压DP
按层DP,枚举每一层出席哪些点,转移即可
设 \(f[i][j]\) 表示曾经增添到第
\(i\) 层,已经支付的汇集为 \(j\) 的纤维代价.
每四回找出集合中的点能扩充到的点,然后dfs枚举拔取什么点增添,加一些剪枝即可
复杂度 \(O(2^{2n}*n)\),加上剪枝可以不满,可是传说枚举补集是
\(O(3^n*n)\) 的?
别的值得注意的是:那样DP会出现众多不合法的气象,然而并不会比法定处境优,所以是实惠的

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define RG register
#define il inline
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
const int N=15;
int map[N][N],dp[N][1<<12],c[N],inf,j,n,m,D;

inline void dfs(int x,int S,int tot){
  if(x==n){
    dp[D+1][j|S]=min(dp[D+1][j|S],dp[D][j]+tot);
    return ;
  }
  if(c[x]!=inf && !(j&(1<<x)))dfs(x+1,S|(1<<x),tot+c[x]);
  dfs(x+1,S,tot);
}

void work()
{
  int x,y,z;
  memset(map,127/3,sizeof(map));
  scanf("%d%d",&n,&m);
  for(int i=1;i<=m;i++){
    scanf("%d%d%d",&x,&y,&z);
    x--;y--;
    map[x][y]=Min(map[x][y],z);
    map[y][x]=map[x][y];
  }
  if(n==1){puts("0");return ;}
  memset(dp,127/3,sizeof(dp));
  memset(c,127/3,sizeof(c));
  int lim=(1<<n)-1;
  inf=dp[0][0];
  for(int i=0;i<n;i++)dp[1][1<<i]=0;
  for(int i=1;i<n;i++){
    D=i;
    for(j=1;j<lim;j++){
      for(int k=0;k<n;k++)c[k]=inf;
      for(int k=0;k<n;k++){
    if(!((1<<k)&j))continue;
    for(RG int l=0;l<n;l++){
      if(((1<<l)&j) || map[k][l]==inf)continue;
      c[l]=min(c[l],map[k][l]*i);
    }
      }
      dfs(0,0,0);
    }
  }
  int ans=2e9;
  for(int i=1;i<n;i++)ans=min(ans,dp[i][lim]);
  printf("%d\n",ans);
}

int main()
{
  work();
  return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图