本文主要是介绍UVA 12223 - Moving to Nuremberg（树形DP），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：12223 - Moving to Nuremberg
题目大意：给定一颗无根树，有一些结点需要访问num次。然后你现在选择一个点作为起点，去访问每个点，访问完要回到原点，求一个起点，使得访问完所有点的路程最少，问这个路程，并求出这些点（如果有多个点一样小都要输出）。
思路：这题是由父亲结点u的状态去推出子节点v状态。如图：
dp[u]为结点u的最佳方案，num[v]为根节点v的子树的总次数，那么要由dp[u]去推出dp[v]，那么g[u][v]这条路对于v后面的点（图中蓝色点）一共会少走num[v] * g[u][v] * 2,对于v前面的点（图中红色点）一共会多走(sum(总次数) - num[v]) * g[u][v] * 2;所以状态转移方程为：dp[v] = dp[u] + (sum - num[v]) * w - num[v] * w; (这里w是路径的两倍)。
然后要进行两遍dfs，第一遍预处理是num数组，并且求出dp[1]的值，第二遍就是树形DP。
代码：
#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;
#define min(a,b) ((a)<(b)?(a):(b))
const int N = 50005;
int t, n, m, vis[N];
typedef long long ll;
ll dp[N], num[N], minv, sum;
struct Node {int v;ll w;Node(){}Node(int vv, ll ww) {v = vv; w = ww;}
};
vector<Node> g[N];void dfs1(int u, ll len) {vis[u] = 1;dp[1] += len * num[u];for (int i = 0; i < g[u].size(); i++) {ll w = g[u][i].w * 2;int v = g[u][i].v;if (vis[v]) continue;dfs1(v, len + w);num[u] += num[v];}
}void dfs2(int u) {vis[u] = 1;minv = min(dp[u], minv);for (int i = 0; i < g[u].size(); i++) {ll w = g[u][i].w * 2;int v = g[u][i].v;if (vis[v]) continue;dp[v] = dp[u] + (sum - num[v]) * w - num[v] * w;dfs2(v);}
}int main() {scanf("%d", &t);while (t--) {memset(vis, 0, sizeof(vis));memset(g, 0, sizeof(g));dp[1] = 0;sum = 0;scanf("%d", &n);int u, v;ll w;for (int i = 1; i < n; i++) {scanf("%d%d%lld", &u, &v, &w);g[u].push_back(Node(v, w));g[v].push_back(Node(u, w));}scanf("%d", &m);memset(num, 0, sizeof(num));while (m--) {scanf("%d%lld", &u, &w);sum += w;num[u] = w;}dfs1(1, 0);memset(vis, 0, sizeof(vis));minv = dp[1];dfs2(1);printf("%lld\n", minv);int bo = 0;for (u = 1; u <= n; u++) {if (dp[u] == minv) {if (bo++) printf(" ");printf("%d", u);}}printf("\n");}return 0;
}
这篇关于UVA 12223 - Moving to Nuremberg（树形DP）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
