题目
给n个节点的带权树,删掉其中一边,就会变成两颗子树,
求删去某条边使得这这两颗子树的 权值之差的绝对值最小。
思路
直接dfs一次,计算所有子树的权值总和tot[i]
如果删掉一条边 (v, fa),fa是v的父亲节点,
那么v子树权值总和为tot[v],显然另一棵子树的权值总和就是sum-tot[v] ,
最总取最小绝对值即可。
这题要注意用long long
其实就是dfs+枚举,想不通为什么有人会 把这题列为树形dp?
代码
/**===================================================== * This is a solution for ACM/ICPC problem * * @source : poj-3140 Contestants Division * @description : 树形dp, 计数问题 * @author : shuangde * @blog : blog.csdn.net/shuangde800 * @email : zengshuangde@gmail.com * Copyright (C) 2013/08/31 14:45 All rights reserved. *======================================================*/ #include <iostream> #include <cstdio> #include <algorithm> #include <vector> #include <queue> #include <cmath> #include <cstring> using namespace std; typedef long long int64; const int INF = 0x3f3f3f3f; const int MAXN = 100010; namespace Adj { int size, head[MAXN]; struct Node{ int v, next; }E[MAXN*2]; inline void initAdj(){ size = 0; memset(head, -1, sizeof(head)); } inline void addEdge(int u, int v) { E[size].v = v; E[size].next = head[u]; head[u] = size++; } } using namespace Adj; int n, m; int num[MAXN]; int64 ans, sum; // http://www.bianceng.cn int64 Abs(int64 a) { return a<0?-a:a; } int64 dfs(int u, int fa) { int64 tot = num[u]; for (int e = head[u]; e != -1; e = E[e].next) { int v = E[e].v; if (v == fa) continue; tot += dfs(v, u); } ans = min(ans, Abs(sum-tot-tot)); return tot; } int main(){ int cas = 1; while (~scanf("%d%d", &n, &m) && n + m) { sum = 0; for (int i = 1; i <= n; ++i) { scanf("%d", &num[i]); sum += num[i]; } initAdj(); for (int i = 0; i < m; ++i) { int u, v; scanf("%d%d", &u, &v); addEdge(u, v); addEdge(v, u); } ans = sum; dfs(1, -1); cout << "Case " << cas++ << ": " << ans << endl; } return 0; }
以上是小编为您精心准备的的内容,在的博客、问答、公众号、人物、课程等栏目也有的相关内容,欢迎继续使用右上角搜索按钮进行搜索int
, 这题怎么做啊
, include
, head
, 求总和
, 树形
, size
总和
contestants、ca3140、argox cp 3140l、施乐3140硒鼓、道康宁3140,以便于您获取更多的相关知识。
时间: 2024-08-31 23:34:03