UVA 1669 Holiday's Accommodatio——树形dp

UVA 1669 Holiday's Accommodatio——树形dp

经过简单分析可以发现题目结果和每条边的遍历次数密切相关。

而遍历次数又和子树点的个数密切相关，所以我们可以从根节点出发进行树形dp，dp【i】维护的是以i为根节点（包括i）的子树的节点个数。

然后考虑状态转移方程，在这之前我们假设整棵树的根节点是1，那么除了1之外每个点都可以对应一条边，这是树形dp问题中将点和边关联的常用操作，这样关联以后我们就可以用ans【i】表示i节点对应的边的最大通过次数（顺便乘以边权），ans【i】=min（dp【i】，n-dp【i】）*cost【i】*2，这个仔细琢磨一下就好了，不用解释了，最后结果就是n-1个ans【i】的和

#include #include #include #include #include using namespace std;typedef pair P;const int maxn = 1e5 + 10;const int INF = 0x3f3f3f3f;int T, n, dp[maxn];long long ans;vector

G[maxn];void dfs(int u, int f) { dp[u] = 1; for (int i = 0; i < G[u].size(); i++) { int v = G[u][i].first, cost = G[u][i].second; if (v == f) continue; dfs(v, u); ans += min(dp[v], n-dp[v])*cost*2; dp[u] += dp[v]; }}int main() { scanf("%d", &T); for (int kase = 1; kase <= T; kase++) { scanf("%d", &n); for (int i = 0; i <= n; i++) G[i].clear(); for (int i = 1; i <= n - 1; i++) { int u, v, cost; scanf("%d %d %d", &u, &v, &cost); G[u].push_back(make_pair(v, cost)); G[v].push_back(make_pair(u, cost)); } ans = 0; dfs(1, 0); printf("Case #%d: %lld\n", kase, ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。