1.题目描述
拼多多王国的城市和道路的拓扑结构比较特别，是一个树状结构：
- 每个城市是树的一个节点；
- 城市之间的道路是树的一条边；
- 树的根节点是首都。
拼多多周年庆马上就要到了，这是拼多多王国的一个大日子。为了活跃气氛，国王想在道路上布置花灯。花灯可是很贵的东西，尽管国王想要在所有道路上都布置花灯，但是如果要花太多钱的话，是过不了财政大臣那一关的。国王把这个计划告诉财政大臣，最后他们商讨出来这么一个方案：
- 一条道路要么不布置花灯，要么整条布置花灯，不能选择其中的某一段布置；
- 除非没有道路通向首都，否则至少为一条通向首都的道路布置花灯；
- 所有布置花灯的道路构成的子图是连通的，这保证国王从首都出发，能通过只走布置了花灯的道路，把所有的花灯游览完；
- 如果某个城市（包括首都）有大于等于2条道路通向子城市，为了防止铺张浪费，最多只能选择其中的两条路布置花灯；
- 布置花灯的道路的总长度设定一个上限。
在上述方案下，国王想要使得布置花灯的道路长度越长越好，你帮国王想想办法。
- 输入描述:
每个测试输入包含1个测试用例。 输入的第一行是一个正整数m，0<m<=9900，表示布置花灯的道路的总长度的上限。 输入的第二行是一个正整数n，n<=100，表示城市的个数。 紧接着是n-1行输入，每行三个正整数u、v、d，表示下标为u的城市有一条长度为d的道路通向它的一个子城市v，其中 0<=u<n，0<=v<n，0<d<=100。 - 输出描述:
输出一个正整数，表示能布置花灯的道路长度的最大值 - 输入示例:
5 5 0 1 1 0 2 2 0 3 3 0 4 4 - 输出示例:
5
2.题目解析
dfs搜索所有可能路径的长度值。包括一个节点所有的儿子中选1个儿子，选2个儿子的情况。
后序深度遍历
建表，把所有的情况统计出来。
本题可以通过树形动态规划的方法去做，具体算法过程是：
- 先对所有节点排一个拓扑序，保证对于每个节点，它的父节点都排在它后面，这个排序可以通过一次树的后序遍历得到；
- 对每个节点，记录一个集合
S，S存的是以当前节点作为根节点的子树下，所有方案的总长度的所有可能值； - 按照步骤1得到的拓扑序遍历所有节点，对每个节点
u，假设它的集合为Su，我们枚举三种情况：
a) 一个子节点都不选，只要往Su集合里面插入0即可；
b) 只选择一个子节点，则枚举所有子节点，假设某个子节点当前记录的集合为Sv，道路长度为d，那 么对Sv里面的所有元素都加上d，插入到Su；
c) 选择两个子节点，则枚举所有两个子节点的组合，类似3a的做法，把所有可能性插入到Su； - 最后看一下根节点中的
S集合里面小于等于上限值m的最大值就是答案。
3.参考答案
#include <bits/stdc++.h>
using namespace std;
struct ChildInfo{
int child; // 子城市下标
int distance; // 到子城市的距离
};
void dfs(vector<vector<ChildInfo> > &lnk, int u, vector<int> &seq) {
for (int k = 0; k != lnk[u].size(); ++k) {
dfs(lnk, lnk[u][k].child, seq);
}
seq.push_back(u);
}
int main() {
int m = 0; // 花灯道路总长度上限
int n = 0; // 城市个数
while (scanf("%d%d", &m, &n) == 2) {
vector<vector<ChildInfo> > lnk(n); // 下标是父城市，元素是子程序与距离数组
vector<int> in(n, 0);// 子城市统计
for (int i = 1; i < n; ++i) {
int u = 0; // 父城市
int v = 0; // 子城市
int d = 0; // 距离
scanf("%d%d%d", &u, &v, &d);
in[v]++;
// 构建树
lnk[u].push_back(ChildInfo{v, d});
}
// 查找根节点
int root; // 根节点
for (int i = 0; i < n; ++i) {
if (in[i] == 0) {
root = i;
break;
}
}
// 后序遍历，排列城市顺序
vector<int> seq;
dfs(lnk, root, seq);
// 统计
vector<int> mem[n];
for (int i = 0; i != n; ++i) {
int u = seq[i];
// 第一种情况，不选择
mem[u].push_back(0);
// 第二种情况，选择一个子城市
for (int k = 0; k != lnk[u].size(); ++k) {
int v = lnk[u][k].child;
int dist = lnk[u][k].distance;
vector<int> memv = mem[v];
for (auto &value : memv) {
int d = value + dist;
if(mem[u].end() == find(mem[u].begin(),mem[u].end(),d)){
mem[u].push_back(d);
}
}
}
// 第三种情况，选择两个子城市
for (int k1 = 0; k1 != lnk[u].size(); ++k1)
for (int k2 = k1 + 1; k2 != lnk[u].size(); ++k2) {
int v1 = lnk[u][k1].child;
int dist1 = lnk[u][k1].distance;
vector<int> memv1 = mem[v1];
int v2 = lnk[u][k2].child;
int dist2 = lnk[u][k2].distance;
vector<int> memv2 = mem[v2];
for (auto &value1 : memv1)
for (auto &value2 : memv2) {
int d = value1 + dist1 + value2 + dist2;
if(mem[u].end() == find(mem[u].begin(),mem[u].end(),d)){
mem[u].push_back(d);
}
}
}
}
// 找到满足条件的最大值
int result = 0;
for (auto &value : mem[root])
if (value <= m) { // 必须小于花灯道路总长度上限
result = max(result, value);
}
printf("%d\n", result);
}
return 0;
}
