題目大意

給出一棵樹，要求你為樹上的結點標上權值，權值可以是任意的正整數 唯一的限制條件是相臨的兩個結點不能標上相同的權值，要求一種方案，使得整棵樹的總價值最小。N<=10000

題解

我們可以猜一個結論,用到的編號不會超過某一個值
我們發現我們可以開到100以上都不會超時
所以我們把編號最多100算,跑樹形dp即可
其實可以證明編號不會超過logn...

Code

#include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; inline void read(int &x){x=0;char ch;bool flag = false;while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x; } inline int cat_max(const int &a,const int &b){return a>b ? a:b;} inline int cat_min(const int &a,const int &b){return a<b ? a:b;} const int maxn = 10010; struct Edge{int to,next; }G[maxn<<1]; int head[maxn],cnt; void add(int u,int v){G[++cnt].to = v;G[cnt].next = head[u];head[u] = cnt; } inline void insert(int u,int v){add(u,v);add(v,u); } int f[maxn][22],g[maxn][4]; const int inf = 0x3f3f3f3f; const int colnum = 3; #define v G[i].to void dfs(int u,int fa){for(int i=1;i<=colnum;++i) f[u][i] = i;for(int i = head[u];i;i=G[i].next){if(v == fa) continue;dfs(v,u);for(int j=1;j<=colnum;++j){if(g[v][0] == f[v][j]) f[u][j] += g[v][1];else f[u][j] += g[v][0];}}g[u][0] = g[u][1] = inf;int pos = -1;for(int i=1;i<=colnum;++i){if(f[u][i] < g[u][0]) g[u][0] = f[u][i],pos = i;}for(int i=1;i<=colnum;++i){if(i == pos) continue;g[u][1] = min(g[u][1],f[u][i]);} } #undef v int main(){int n;read(n);int u,v;for(int i=1;i<n;++i){read(u);read(v);insert(u,v);}dfs(1,0);printf("%d\n",g[1][0]);getchar();getchar();return 0; }

轉載于:https://www.cnblogs.com/Skyminer/p/6417320.html

總結

以上是生活随笔為你收集整理的bzoj 1369: Gem 树形dp的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。