东营的招聘网站哪个有用,天津的网站建设公司哪家好,2021网站你懂我意思正能量,网站建设 推广问题描述
人类在火星上发现了一种新的金属#xff01;这些金属分布在一些奇怪的地方#xff0c;不妨叫它节点好了。一些节点之间有道路相连#xff0c;所有的节点和道路形成了一棵树。一共有 n 个节点#xff0c;这些节点被编号为 1~n 。人类将 k 个机器人送上了火星…问题描述
人类在火星上发现了一种新的金属这些金属分布在一些奇怪的地方不妨叫它节点好了。一些节点之间有道路相连所有的节点和道路形成了一棵树。一共有 n 个节点这些节点被编号为 1~n 。人类将 k 个机器人送上了火星目的是采集这些金属。这些机器人都被送到了一个指定的着落点 S 号节点。每个机器人在着落之后必须沿着道路行走。当机器人到达一个节点时它会采集这个节点蕴藏的所有金属矿。当机器人完成自己的任务之后可以从任意一个节点返回地球。当然回到地球的机器人就无法再到火星去了。我们已经提前测量出了每条道路的信息包括它的两个端点 x 和 y以及通过这条道路需要花费的能量 w 。我们想花费尽量少的能量采集所有节点的金属这个任务就交给你了。
输入格式
第一行包含三个整数 n, S 和 k 分别代表节点个数、着落点编号和机器人个数。
接下来一共 n-1 行每行描述一条道路。一行含有三个整数 x, y 和 w 代表在 x 号节点和 y 号节点之间有一条道路通过需要花费 w 个单位的能量。所有道路都可以双向通行。
输出格式
输出一个整数代表采集所有节点的金属所需要的最少能量。 思路如下
代码
#includebits/stdc.h
#define endl \n
using namespace std;
typedef long long ll;
const int N1e510,mod1e97;//(1ll63)-1 vectorpairint,int e[N];
int dp[N][15];
int n,s,k;
void dfs(int u,int fa)
{ for(int i0;ie[u].size();i) { int ve[u][i].first,we[u][i].second; if(vfa)continue; dfs(v,u); for(int jk;j0;j--)//顺序遍历会影响后面的状态 { dp[u][j]dp[v][0]w*2;//m0 for(int m1;mj;m) dp[u][j]min(dp[u][j],dp[u][j-m]dp[v][m]w*m); } }
}
void solve()
{ cinnsk; for(int i0;in-1;i) { int u,v,w; cinuvw; e[u].push_back({v,w}); e[v].push_back({u,w}); } dfs(s,0); coutdp[s][k]endl;
}
int main()
{ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); int T1; //cinT; while(T--) { solve(); } return 0;
}
