BZOJ1369: [Baltic2003]Gem 树形DP

BZOJ 1369: [Baltic2003]Gem

Time Limit: 2 Sec   Memory Limit: 64 MB Submit: 343   Solved: 219 [Submit][Status][Discuss] 题解： TreeDP，每个点的颜色大概8种就够了 #include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int N=10005; const int M=20005; int cnt,to[M],lj[N],nxt[M]; void insert(int f,int t) { cnt++,to[cnt]=t,nxt[cnt]=lj[f],lj[f]=cnt; cnt++,to[cnt]=f,nxt[cnt]=lj[t],lj[t]=cnt; } int n,f[N][9],fa[N]; void dfs(int x) { for(int i=lj[x];i;i=nxt[i]) if(to[i]!=fa[x]) { fa[to[i]]=x; dfs(to[i]); for(int j=1;j<=8;j++) { int mn=1e9; for(int k=1;k<=8;k++) if(k!=j) mn=min(mn,f[to[i]][k]); f[x][j]+=mn; } } for(int i=1;i<=8;i++) f[x][i]+=i; } int main() { scanf("%d",&n); for(int i=1;i<n;i++) { int x,y; scanf("%d%d",&x,&y); insert(x,y); } dfs(1); int ans=1e9; for(int i=1;i<=8;i++) ans=min(ans,f[1][i]); printf("%d",ans); }

Description

给出一棵树，要求你为树上的结点标上权值，权值可以是任意的正整数 唯一的限制条件是相临的两个结点不能标上相同的权值，要求一种方案，使得整棵树的总价值最小。

Input

先给出一个数字N,代表树上有N个点,N<=10000 下面N-1行,代表两个点相连

Output

最小的总权值

Sample Input

10 7 5 1 2 1 7 8 9 4 1 9 7 5 6 10 2 9 3

Sample Output

14

HINT

Source

[Submit][Status][Discuss]