題目描述：
一棵N(N<5,000)個(gè)節(jié)點(diǎn)的樹，染兩種顏色，不同顏色不能相鄰且要給盡可能多的節(jié)點(diǎn)染色。求顏色A和顏色B可能的染色節(jié)點(diǎn)個(gè)數(shù)。
算法分析：
顯然是只有一個(gè)節(jié)點(diǎn)不染色的時(shí)候最優(yōu)，之前要求出這個(gè)節(jié)點(diǎn)所有子樹的孩子的個(gè)數(shù)，這個(gè)需要樹形DP。
然后每個(gè)不染色的節(jié)點(diǎn)，哪些孩子染哪些顏色，有多少不同的數(shù)量，這個(gè)是背包。
然后讓我糾結(jié)的是，為啥大家都把背包當(dāng)水題做？
#include<iostream>
#include<cstdio>
using namespace std;
const int V = 5005;
const int E = V<<1;
int n,e,head[V],nxt[E],pnt[E];
bool ans[V],dp[V][V];
void add(int u,int v){
nxt[e] = head[u]; head[u]=e;pnt[e] = v;e++;
}
int sum[V];
void dfs(int u,int f){
sum[u] = 1;
dp[u][0] = 1;
for(int i=head[u];i!=-1;i=nxt[i]){
int v = pnt[i];
if(v==f) continue;
dfs(v,u);
sum[u] += sum[v];
for(int i=n-1;i>=0;i--)
if(dp[u][i])
dp[u][i + sum[v]] = 1;
}
int s = n-sum[u];
for(int i=n-1;i>=0;i--)
if(dp[u][i]) dp[u][i+s] = 1;
// cout<<"u: "<<u<<endl;
// for(int i=0;i<n;i++) if(dp[u][i]) cout<<i<<" "; cout<<endl;
for(int i=0;i<n;i++)
ans[i] |= dp[u][i];
}
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++) head[i] = -1;
int u,v;
e = 0;
for(int i=1;i<n;i++){
scanf("%d%d",&u,&v);
u--; v--;
add(u,v);
add(v,u);
}
dfs(0,0);
int len = 0;
for(int i=1;i<n-1;i++)
len += ans[i];
printf("%d\n",len);
for(int i=1;i<n-1;i++) if(ans[i]){
printf("%d %d\n",i,n-1-i);
}
return 0;
}
posted on 2012-07-21 22:47
西月弦 閱讀(286)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
解題報(bào)告