首页 > 代码库 > 4711: 小奇挖矿
4711: 小奇挖矿
4711: 小奇挖矿
Description
【题目背景】
小奇在喵星系使用了无限非概率驱动的采矿机，以至于在所有星球上都采出了一些矿石，现在它准备建一些矿石仓
库并把矿石运到各个仓库里。
【问题描述】
喵星系有n个星球，标号为1到n，星球以及星球间的航线形成一棵树。所有星球间的双向航线的长度都为1。小奇要
在若干个星球建矿石仓库，设立每个仓库的费用为K。对于未设立矿石仓库的星球，设其到一个仓库的距离为i，则
将矿石运回的费用为Di。请你帮它决策最小化费用。
Input
第一行2个整数n，K。
第二行n-1个整数，D1,D2,…Dn-1,保证Di<=Di+1。
接下来n-1行，每行2个整数x，y，表示星球x和星球y存在双向航线。
n<=200，0<=K，Di<=100000
Output
输出一行一个整数，表示最小费用。
Sample Input
8 10
2 5 9 11 15 19 20
1 4
1 3
1 7
4 6
2 8
2 3
3 5
2 5 9 11 15 19 20
1 4
1 3
1 7
4 6
2 8
2 3
3 5
Sample Output
38
【样例解释】
在1，2号星球建立仓库。
【样例解释】
在1，2号星球建立仓库。
题解：
貌似是讲课时候某道题的弱化版（当时听得云里雾里）。。。
f[i][j]表示在i的子树中，i走到j（但还没算花费），并且其他走到不同地方的点都算了花费的最优值。
然后转移吧。。
#include<stdio.h>#include<iostream>using namespace std;const int N=205;int n,m,i,x,y,a[N],d[N][N],g[N],f[N][N];int tot,head[N],to[N<<1],Next[N<<1];void add(int x,int y){ to[tot]=y; Next[tot]=head[x]; head[x]=tot++;}inline void dfs(int now,int x,int pre){ for(int i=head[x];i!=-1;i=Next[i]) if(to[i]!=pre) { d[now][to[i]]=d[now][x]+1; dfs(now,to[i],x); }}inline void Dfs(int x,int pre){ for(int i=head[x];i!=-1;i=Next[i]) if(to[i]!=pre) Dfs(to[i],x); g[x]=1e9; for(int i=1;i<=n;i++) { f[x][i]+=a[d[x][i]]; for(int j=head[x];j!=-1;j=Next[j]) if(to[j]!=pre) f[x][i]+=min(f[to[j]][i],g[to[j]]+m); g[x]=min(g[x],f[x][i]); }}int main(){ scanf("%d%d",&n,&m); for(i=1;i<=n;i++) head[i]=-1; for(i=1;i<n;i++) scanf("%d",&a[i]); for(i=1;i<n;i++) { scanf("%d%d",&x,&y); add(x,y);add(y,x); } for(i=1;i<=n;i++) dfs(i,i,0); Dfs(1,0); cout<<g[1]+m; system("pause"); return 0;}
4711: 小奇挖矿
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。