首页 > 代码库 > UVA 12452 Plants vs. Zombies HD SP 树形dp(水
UVA 12452 Plants vs. Zombies HD SP 树形dp(水
题目链接:点击打开链接
题意:
给定n个点的树[0,n)
开始所有边都是无色。
有3种操作:
1、选一个点染其相连的边 花费100
2、选一个点染其相连的2条边 花费175
3、选一个点染其相连的所有边 花费500
问:
染完所有边的最小花费。边可以重复染,点只能被操作一次。
#include <string> #include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <cstring> #include <queue> #include <set> #include <map> #include <vector> template <class T> inline bool rd(T &ret) { char c; int sgn; if(c=getchar(),c==EOF) return 0; while(c!='-'&&(c<'0'||c>'9')) c=getchar(); sgn=(c=='-')?-1:1; ret=(c=='-')?0:(c-'0'); while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0'); ret*=sgn; return 1; } template <class T> inline void pt(T x) { if (x <0) { putchar('-'); x = -x; } if(x>9) pt(x/10); putchar(x%10+'0'); } using namespace std; typedef long long ll; const int N = 10100; const ll inf = 1e10; struct Edge{ int to, nex; }edge[N<<1]; int head[N], edgenum; void add(int u, int v){ Edge E = {v, head[u]}; edge[edgenum] = E; head[u] = edgenum++; } void init(){memset(head, -1, sizeof head); edgenum = 0;} int n; ll dp[N][2]; /* dp[i][0] : i的父边选了 dp[i][1] : i的父边不选 */ void up(ll &x, const ll &y){ if(y<x)x = y; } void dfs(int u, int fa){ dp[u][0] = dp[u][1] = inf; bool isleaf = true; ll a[3]; memset(a, 0, sizeof a); for(int i = head[u]; ~i; i = edge[i].nex){ int v = edge[i].to; if(v == fa)continue; dfs(v, u); a[0] += dp[v][0]; a[1] += dp[v][1]; a[2] += min(dp[v][0], dp[v][1]); isleaf = false; } if(isleaf) {dp[u][0] = 100; dp[u][1] = 0;return; } /////// up(dp[u][0], a[0]+100); up(dp[u][0], a[2]+500); up(dp[u][1], a[0]); ll b[3]; b[0] = b[1] = inf; for(int i = head[u]; ~i; i = edge[i].nex){ int v = edge[i].to; if(v == fa)continue; up(dp[u][0], a[0]-dp[v][0]+dp[v][1] + 175); b[2] = -dp[v][0]+dp[v][1]; sort(b, b+3); } up(dp[u][1], a[0]+b[0]+b[1]+175); } void input(){ init(); rd(n); for(int i = 1, u, v; i < n; i++){ rd(u); rd(v); add(u, v); add(v, u); } } int main() { int T;scanf("%d", &T); while(T--){ input(); dfs(0, 0); // for(int i = 0; i < n; i++)printf("%d: %lld %lld\n", i, dp[i][0], dp[i][1]); printf("$%lld\n", min(dp[0][0], dp[0][1])); } return 0; } /* 99 10 0 1 0 2 3 2 2 4 3 5 3 6 3 7 3 8 3 9 6 0 1 0 2 0 3 3 4 4 5 7 0 1 1 2 2 3 2 4 2 5 5 6 5 0 1 0 2 0 3 3 4 5 0 1 0 2 0 3 0 4 7 0 1 0 2 0 3 0 4 0 5 0 6 7 0 1 0 2 1 3 3 4 5 2 5 6 */
UVA 12452 Plants vs. Zombies HD SP 树形dp(水
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。