算法概论实验七

算法概论实验

实验七
实验目的与要求：
（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;  
}