首页 / C++ / C++ API 设计 03 序言
C++ API 设计 03 序言
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了C++ API 设计 03 序言,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含3805字,纯文字阅读大概需要6分钟。
内容图文
![C++ API 设计 03 序言](/upload/InfoBanner/zyjiaocheng/1097/f06df7de0948430bb93677b029364f9f.jpg)
It is said that the people of Menggol lived in caves. A tribe‘s caves were connected to each other with paths. The paths were so designed that there was one and only one path to each cave. So the caves and the paths formed a tree. There was a main cave, which connected the world outside. The Menggolian always carved a map of the tribe‘s caves on the wall of the main cave.
Scientists have just discovered Menggolian‘s tribe. What a heart-stirring discovery! They are eager to explore it. Since the terrain is very complex and dangerous, they decide to send out a robot.
The robot will be landed into the main cave, where he will begin his adventure. It doesn‘t have to return to the main cave, because the messages of his exploration will be sent immediately to the scientists while he is on the way.
A robot can only walk x meters before it runs out of energy. So the problem arises: given the map of the tribe‘s caves and a set of x , how many caves can be explored at most?
Input
There are multiple test cases in the input file. Each test case starts with a single number n (0
Output
For each test case, output q lines in the format as indicated in the sample output, each line contains one integer, the maximum number of caves the robot is able to visit.
Sample Input
3 1 0 5 2 0 3 3 3 10 11 0
Sample Output
Case 1: 2 2 3
题意:一个n结点的有根树,树边权均为正数,现在有q次询问,每次询问一个距离,问这个距离最多能经过多少点,同一结点多次经过算1次。
思路:树形dp,状态的表示为dp[u][j][0]表示根为u的树,遍历j个点,不返回u所需的最小距离,dp[u][j][1]则表示返回u的最小距离。这样的话就是根v的树查找k个点,根u的树查找j-k个点,之和就是j。状态转移方程为:
如此一来dp[u][j][1] = min{dp[v][k][1] + dp[u][j - k][1] + 2 * g[u][v].value);
dp[u][j][0] = min(dp[v][k][0] + dp[u][j - k][1] + g[u][v].value, dp[v][k][1] + dp[u][j - k][0] + 2 * g[u][v].value);
代码:
#include <stdio.h> #include <string.h> #include <vector> #define INF 0x3f3f3f3f #define min(a,b) ((a)<(b)?(a):(b)) using namespace std; const int N = 505; int n, q, u, v, value, num, i, vis[N], dp[N][N][2], sum[N]; struct Node { int v, value; Node() {} Node(int vv, int vva) {v = vv; value = vva;} }; vector<Node> g[N]; void dfs(int u) { vis[u] = sum[u] = 1; dp[u][1][0] = dp[u][1][1] = 0; for (int i = 0; i < g[u].size(); i++) { int v = g[u][i].v, value = g[u][i].value; if (vis[v]) continue; dfs(v); sum[u] += sum[v]; for (int j = sum[u]; j > 1; j--) { for (int k = 0; k <= j && k <= sum[v]; k++) { dp[u][j][1] = min(dp[u][j][1], dp[u][j - k][1] + dp[v][k][1] + 2 * value); dp[u][j][0] = min(dp[u][j][0], dp[u][j - k][1] + dp[v][k][0] + value); dp[u][j][0] = min(dp[u][j][0], dp[u][j - k][0] + dp[v][k][1] + 2 * value); } } } } int main() { int cas = 0; while (~scanf("%d", &n) && n) { memset(vis, 0, sizeof(vis)); memset(g, 0, sizeof(g)); for (i = 0; i < n - 1; i++) { scanf("%d%d%d", &v, &u, &value); g[u].push_back(Node(v, value)); g[v].push_back(Node(u, value)); } memset(dp, INF, sizeof(dp)); dfs(0); scanf("%d", &q); printf("Case %d:\n", ++cas); while (q--) { scanf("%d", &num); for (int i = n; i >= 1; i--) { if (dp[0][i][0] <= num || dp[0][i][1] <= num) { printf("%d\n", i); break; } } } } return 0; }
原文:http://blog.csdn.net/patriot074/article/details/19856013
内容总结
以上是互联网集市为您收集整理的C++ API 设计 03 序言全部内容,希望文章能够帮你解决C++ API 设计 03 序言所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。