首页 > 程序开发 > 综合编程 > 其他综合 >

UVA1220 树形DP

2017-02-17

UVA1220 树形DP:n个人,第一个人为老板,剩下n-1行,第一个字符串为员工名称,第二个字符串为上级名称。当选择上级的时候便不能再选择下级,求最多能选多少人,以及选择方案是否唯一。

UVA1220 树形DP:n个人,第一个人为老板,剩下n-1行,第一个字符串为员工名称,第二个字符串为上级名称。当选择上级的时候便不能再选择下级,求最多能选多少人,以及选择方案是否唯一。

题解

树的最大独立集问题。设d[u][0]为以u为根的子树,若不选择员工u可得到的最大人数,f[u][0]为方案唯一性,0代表不唯一,1代表唯一。d[u][1]为选择员工u可得到的最大人数,f[u][1]同理。由此可得两套状态转移方程,d[u][1]=sum(d[v][0])(v为u的子节点),当且仅当所有f[v][0]=1时,f[u][1]=1。d[u][0]=sum(max(d[v][0],d[v][1])),d[v][0]==d[v][1]时,f[u][0]=0,max值对应的方案不唯一时,f[u][0]=0。

注意事项

注意有的样例上级没有在员工那一列出现过就被使用,因此在输入处理的时候,需要一个整数num,当上级没有出现过的时候,num++,并记录上级名称。

代码
#include 
#include
#include
#include
#include
#include

using namespace std;
map mp;
vector vt[210];
int dp[210][2];
int f[210][2];

void dfs(int u){
    if(vt[u].empty()){
        dp[u][0]=0;
        dp[u][1]=1;
        return ;
    }
    //printf("%d %d ",u,vt[u].size());
    int k=vt[u].size();
    for(int i=0;idp[vt[u][i]][0]){
            dp[u][0]+=dp[vt[u][i]][1];
            if(f[vt[u][i]][1]==0){
                f[u][0]=0;
            }
        }else{
            dp[u][0]+=dp[vt[u][i]][0];
            if(dp[vt[u][i]][1]==dp[vt[u][i]][0]){
                f[u][0]=0;
            }else if(f[vt[u][i]][0]==0){
                f[u][0]=0;
            }
        }
    }
    dp[u][1]++;
}

int main()
{
    //freopen("d://input.txt","r",stdin);
    //freopen("d://output.txt","w",stdout);
    int n;
    while(scanf("%d",&n)){
        if(n==0)
            break;
        mp.clear();
        memset(dp,0,sizeof(dp));
        memset(vt,0,sizeof(vt));
        for(int i=0;i<=n;i++){
            f[i][0]=1;
            f[i][1]=1;
        }

        string str,son;
        cin>>str;
        int num=1;
        mp[str]=num++;
        for(int i=1;i>son;
            if(!mp[son]){
                mp[son]=num++;
            }
            cin>>str;
            if(!mp[str]){
                mp[str]=num++;
            }
            vt[mp[str]].push_back(mp[son]);
        }

        dfs(1);
        if(dp[1][1]>dp[1][0]){
            printf("%d ",dp[1][1]);
            if(f[1][1]){
                printf("Yes\n");
            }else{
                printf("No\n");
            }
        }else if(dp[1][1]==dp[1][0]){
            printf("%d No\n",dp[1][1]);
        }else{
            printf("%d ",dp[1][0]);
            if(f[1][0]){
                printf("Yes\n");
            }else{
                printf("No\n");
            }
        }
    }
    return 0;
}
相关文章
最新文章
热点推荐