首页 > 代码库 > hdu5148---Cities
hdu5148---Cities
Cities
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 355 Accepted Submission(s): 122
Problem Description
Long long ago,there is a knight called JayYe.He lives in a small country.This country is made up of n cities connected by n-1 roads(that means it‘s a tree).The king wants to reward JayYe because he beats the devil and save the princess.The king decide to give JayYe exactly K cities as his daughter‘s dowry.
Here comes the question.Although JayYe beats the devil,his knee was injured.So he doesn‘t want to move too much,he wants his citys as close as possible,that is, JayYe wants the expected distance of his cities as small as possible.
The expected distance is defined as the expected distance between node u and node v,both u and v are randomly choose from JayYe‘s K cities equiprobably(that means first choose u randomly from JayYe’s K cities,then choose v randomly from JayYe’s K cities,so the case u equals to v is possible).
Suppose you are the king,please determine the K cities so that JayYe is happy.
Because the author is lazy,you only need tell me the minimum expect distance.
Here comes the question.Although JayYe beats the devil,his knee was injured.So he doesn‘t want to move too much,he wants his citys as close as possible,that is, JayYe wants the expected distance of his cities as small as possible.
The expected distance is defined as the expected distance between node u and node v,both u and v are randomly choose from JayYe‘s K cities equiprobably(that means first choose u randomly from JayYe’s K cities,then choose v randomly from JayYe’s K cities,so the case u equals to v is possible).
Suppose you are the king,please determine the K cities so that JayYe is happy.
Because the author is lazy,you only need tell me the minimum expect distance.
Input
The first line contains a single integer T,indicating the number of test cases.
Each test case begins with two integers n and K,indicating the number of cities in this country,the number of cities the king gives to the knight.Then follows n-1 lines,each line contains three integers a,b,and c, indicating there is a road connects city a and city b with length c.
[Technical Specification]
1 <= T <= 100
1 <= K <= min(50,n)
1 <= n <= 2000
1 <= a,b <= n
0 <= c <= 100000
Each test case begins with two integers n and K,indicating the number of cities in this country,the number of cities the king gives to the knight.Then follows n-1 lines,each line contains three integers a,b,and c, indicating there is a road connects city a and city b with length c.
[Technical Specification]
1 <= T <= 100
1 <= K <= min(50,n)
1 <= n <= 2000
1 <= a,b <= n
0 <= c <= 100000
Output
For each case, output one line, contain one integer, the minimum expect distance multiplyK2 .
Sample Input
1 2 2 1 2 1
Sample Output
2
Source
BestCoder Round #23
Recommend
heyang | We have carefully selected several similar problems for you: 5149 5145 5144 5143 5142
题目要求 sigma(i) sigma(j) d[i][j] / k^2
转换一下就是求sigma(i) sigma(j) d[i][j]
根据题解所说, 每条边会把树分成2份,如果在一部分里选j个点,那么这条边贡献了 j * (k - j) * w * 2的值
所以可以令 dp[u][i] 表示 在以 u为根的子树里选i个点,
dp[u][i] = min(dp[v][j] + dp[u][i- j] + cost);
然后树形dp搞下就行了,为了使dp[u][i- j] 里 不包括 dp[v][j], 在枚举i的时候要逆序,原因和01背包的空间优化原理一样
/************************************************************************* > File Name: hdu5148.cpp > Author: ALex > Mail: 405045132@qq.com > Created Time: 2014年12月23日 星期二 18时04分08秒 ************************************************************************/ #include <map> #include <set> #include <queue> #include <stack> #include <vector> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N = 2010; int n, k, tot; long long dp[N][55]; int head[N]; struct node { int weight; int next; int to; }edge[N << 1]; void addedge(int from, int to, int weight) { edge[tot].weight = weight; edge[tot].to = to; edge[tot].next = head[from]; head[from] = tot++; } void dfs(int u, int fa) { dp[u][0] = 0; dp[u][1] = 0; for (int i = head[u]; ~i; i = edge[i].next) { int v = edge[i].to; int w = edge[i].weight; if (v == fa) { continue; } dfs(v, u); for (int i = k; i >= 1; --i) { for (int j = 1; j <= i; ++j) { long long cost = (long long)2 * j * (k - j) * w; dp[u][i] = min(dp[u][i], dp[u][i - j] + dp[v][j] + cost); } } } } int main() { int t; int u, v, w; scanf("%d", &t); while (t--) { memset (head, -1, sizeof(head)); tot = 0; scanf("%d%d", &n, &k); for (int i = 1; i <= n; ++i) { for (int j = 0; j <= k; ++j) { dp[i][j] = (1ll << 60); } } for (int i = 1; i <= n - 1; ++i) { scanf("%d%d%d", &u, &v, &w); addedge(u, v, w); addedge(v, u, w); } dfs(1, -1); printf("%lld\n", dp[1][k]); } return 0; }
hdu5148---Cities
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。