考古学【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地图