@rg070836rg
2015-11-29T18:10:43.000000Z
字数 1023
阅读 1443
算法概论实验
实验七
实验目的与要求:
(1)掌握树型动态规划方法的基本思想与设计策略。
1.树中的最大独立集问题
【问题描述】
给定一个无回路的无向图(即树),设计一个动态规划算法,求出该图的最大独立集,并输出该集合中的各个顶点值。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN=100;
vector<int> G[MAXN]; //G[i]表示顶点i的邻接点
int l[MAXN]; //结点层次
int p[MAXN]; //根树
int dp[MAXN]; //dp数组
int sumC[MAXN]; //孩子DP和
int sumS[MAXN]; //孙子DP和
int maxL; //最大层次
int n;
void readTree()
{
int u,v;
cin>>n;
for(int i=0;i<n-1;++i)
{
cin>>u>>v;
G[u].push_back(v);
G[v].push_back(u);
}
}
void dfs(int u,int fa)
{
int d=G[u].size();
l[u]= (fa==-1)? 0: (l[fa]+1);
if(l[u]>maxL)
{
maxL=l[u];
}
for(int i=0;i<d;++i)
{
int v=G[u][i];
if(v!=fa)
{
dfs(v,p[v]=u);
}
}
}
int rootDp(int u)
{
//构造u根树
p[u]=-1;
maxL=-1;
dfs(u,p[u]);
for(int i=maxL;i>=0;--i)
{
for(int j=0;j<n;++j)
{
if(l[j]==i)
{
if (sumS[j]+1>sumC[j])
{
dp[j]=sumS[j]+1;
}
else
dp[j] = sumC[j];
if(i-1>=0)
{
sumC[p[j]]+=dp[j];
}
if(i-2>=0)
{
sumS[p[p[j]]]+=dp[j];
}
}
}
}
return dp[u];
}
int main()
{
readTree();
int res=-1;
//分别以每个顶点为根
for(int i=0;i<n;++i)
{
memset(sumS,0,sizeof(sumS));
memset(sumC,0,sizeof(sumC));
int tmp;
if((tmp=rootDp(i))>res)
res=tmp;
}
cout<<res<<endl;
return 0;
}