文物考古

当前位置:东方赌场 > 文物考古 > 【NOIP 2017】宝藏东方赌场网址

【NOIP 2017】宝藏东方赌场网址

来源:http://www.you-jia.com 作者:东方赌场 时间:2019-10-31 20:07

Description

涉足考古发现的小明得到了风流倜傥份藏宝图,藏宝图上标出了 n 个深埋在地下的宝藏屋, 也交给了那 n 个宝藏屋之间可供开拓的 m 条道路和它们的长度。
小明决心亲自前去发掘独具宝藏屋中的宝藏。不过,每种宝藏屋间隔地面都比较远, 也即是说,从地点开采一条到有个别宝藏屋的道路是很困难的,而开拓宝藏屋之间的征途 则相对轻巧比非常多。
小明的决心感动了考古发掘的赞助商,赞助商决定免费支持他打通一条从地点到某些宝藏屋的坦途,通往哪个宝藏屋则由小明来决定
在那基础上,小明还亟需思量什么开凿宝藏屋之间的道路。已经开凿出的征途能够大肆通行不消耗代价。每开凿出一条新征程,小明就能够与考古队一同挖掏出由该条道路 所能达到的财富屋的遗产。别的,小明不想付出无用道路,即多个曾经被打通过的能源屋之间的道路不必要再支付。
新开垦一条道路的代价是:
[L×K]
L代表那条道路的尺寸,K代表从赞助商帮你打通的宝藏屋到那条道路源点的宝藏屋所通过的 宝藏屋的数目(包涵赞助商帮你打通的宝藏屋和那条道路起源的宝藏屋) 。
请您编写程序为小明选定由赞助商打通的宝藏屋和之后开凿的征途,使得工程总代 价最小,并出口那些小小的值。

solution

正解:状压DP
【NOIP 2017】宝藏东方赌场网址。按层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("%dn",ans);
}

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

本文由东方赌场发布于文物考古,转载请注明出处:【NOIP 2017】宝藏东方赌场网址

关键词: