POJ 3140 Contestants Division——树形dp

POJ 3140 Contestants Division——树形dp

m的大小是哄人的，其实m恒等于n-1，然后就是很普通的树形dp了，注意用long long

#include #include #include #include using namespace std;typedef long long ll;const ll INF = 1e12;const int maxn = 1e5 + 10;int n, m;ll dp[maxn];int tot, head[maxn];struct Edge { int to, next;}edge[maxn<<1];void init() { tot = 0; memset(head, -1, sizeof(head));}void addedge(int u, int v) { ++tot; edge[tot].to = v, edge[tot].next = head[u]; head[u] = tot;}void dfs(int u, int p) { for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; if (v == p) continue; dfs(v, u); dp[u] += dp[v]; }}ll iabs(ll x) { return x >= 0 ? x : -x;}int main() { int flag = 0; while (~scanf("%d %d", &n, &m) && (n + m)) { if (m != n - 1) { for (int i = 1; ;i++); } init(); int u, v; ll sum = 0; for (int i = 1; i <= n; i++) { scanf("%lld", &dp[i]); sum += dp[i]; } for (int i = 1; i <= m; i++) { scanf("%d %d", &u, &v); addedge(u, v); addedge(v, u); } dfs(1, -1);// for (int i = 1; i <= n; i++) cout << dp[i] << " ";// cout << endl; ll ans = INF; for (int i = 1; i <= n; i++) { ll a = dp[i], b = sum - dp[i]; ans = min(ans, iabs(a - b)); } printf("Case %d: %lld\n", ++flag, ans); } return 0;}

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