学步园

#include <iostream><br /> #include <vector><br /> #include <algorithm><br /> using namespace std;</p> <p>/*********************************/<br /> * 可以动态变化的邻接矩阵<br /> * G[i]表示顶点i的邻接点<br /> /*********************************/</p> <p>const int MAXN=100;<br /> vector<int> G[MAXN]; //无根树<br /> int l[MAXN]; //结点层次<br /> int p[MAXN]; //根树<br /> int dp[MAXN]; //dp数组<br /> int sumC[MAXN]; //孩子DP和<br /> int sumS[MAXN]; //孙子DP和<br /> int maxL; //最大层次<br /> int n;</p> <p>/*********************************/<br /> * 读入无根树，n顶点,n-1边<br /> /*********************************/</p> <p>void readTree()<br /> {<br /> int u,v;<br /> cin>>n;<br /> for(int i=0;i<n-1;++i)<br /> {<br /> cin>>u>>v;<br /> G[u].push_back(v);<br /> G[v].push_back(u);<br /> }<br /> }</p> <p>/*********************************/<br /> * 以无根树u顶点为根，构造有根树<br /> * 主函数调用dfs(u,-1);<br /> * 测试数据：<br /> 8<br /> 0 1<br /> 1 4<br /> 0 2<br /> 0 3<br /> 1 5<br /> 5 6<br /> 5 7<br /> /*********************************/</p> <p>void dfs(int u,int fa)<br /> {<br /> int d=G[u].size();<br /> l[u]= (fa==-1)? 0: (l[fa]+1);<br /> if(l[u]>maxL)<br /> {<br /> maxL=l[u];<br /> }<br /> for(int i=0;i<d;++i)<br /> {<br /> int v=G[u][i];<br /> if(v!=fa)<br /> {<br /> dfs(v,p[v]=u);<br /> }<br /> }<br /> }</p> <p>int rootDp(int u)<br /> {<br /> //构造u根树<br /> p[u]=-1;<br /> maxL=-1;<br /> dfs(u,p[u]);<br /> for(int i=maxL;i>=0;--i)<br /> {<br /> for(int j=0;j<n;++j)<br /> {<br /> if(l[j]==i)<br /> {<br /> dp[j]=max(sumS[j]+1,sumC[j]);<br /> if(i-1>=0)<br /> {<br /> sumC[p[j]]+=dp[j];<br /> }<br /> if(i-2>=0)<br /> {<br /> sumS[p[p[j]]]+=dp[j];<br /> }<br /> }<br /> }<br /> }<br /> return dp[u];<br /> }</p> <p>int main()<br /> {<br /> readTree();<br /> int best=-1;<br /> //分别以每个顶点为根<br /> for(int i=0;i<n;++i)<br /> {<br /> memset(sumS,0,sizeof(sumS));<br /> memset(sumC,0,sizeof(sumC));<br /> int tmp;<br /> if((tmp=rootDp(i))>best)<br /> {<br /> best=tmp;<br /> }<br /> }<br /> //打印结果看看<br /> cout<<best<<endl;<br /> return 0;<br /> }

Dp: dp[u]=max{ sum(dpS[])+1, sum(dpC[])};

以某一个顶点为根的树,运用此DP公式.

意思是,

如果选结点u,那么dp[u]=孙子结点的dp[]和加自身这个结点1.

如果不选结点u,那么dp[u]=孩子结点的dp[]和.

代码里注释有: 无根树转化有根树算法.

 在算法中,顺便记录了每个结点的层次.

这样,在做刷表DP的时候, 可以很方便的在根树种,按层次从底向上刷表.