【特殊的图+DP】【11月校赛】大家一起玩游戏

大家一起玩游戏

Time Limit : 2000/1000ms (Java/Other) Memory Limit : 65536/32768K (Java/Other)

Total Submission(s) : 26 Accepted Submission(s) : 2

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

Problem Description

n个小朋友一起玩游戏，但是他们中有些人互相讨厌，所以不愿一起玩游戏。而且对于每个小朋友，不会有超过2个讨厌的人。现在每个小朋友有个快乐值，问该怎样从n个小朋友中选出一些人，使他们中不会存在讨厌关系，且快乐值最大。

Input

第一行是case数T(1 <= T <= 100)
接下来有T组case，每组case有 n + 2 行
第一行有一个整数n(1 <= n <= 100) 表示有n个小朋友。
接下来n行，每行以整数k开始，表示第i个小朋友有k个讨厌的人，接着k个数表示他讨厌的小朋友编号。(1 <= k <= 2) 如果i讨厌j，这必然也有j讨厌i。
接下去一行有n个值，表示每个小朋友的快乐值。

Output

对每个case，输出最大的快乐值。

Sample Input

Sample Output

Source

hujie 测试专用(2)

初看还以为是图上的最大独立集问题（权值都为1时）但是因为是k<=2 所以是多个环或者多个链的集合

并不是一个复杂的图，对于环路和简单链直接DP即可

F[i][0] 表示不选第i个节点的前几个节点得到的最大值

F[i][1] 表示选第i个节点的前几个节点得到的最大值

F[i][0]=max(f[i-1][0],F[i][1])

F[i][1]=F[i][0]+wei[i]

环路增加一维判断第一个是否要选即可

#include <cstdio>  
#include <cstdlib>  
#include <cmath>  
#include <cstring>  
#include <ctime>  
#include <algorithm>  
#include <iostream>
#include <sstream>
#include <string>
#define oo 0x13131313   
using namespace std;
int MAP[103][3];
int wei[103];
int visit[103];
int F[103][3][3];
int n,m;
int temp;
int ans=0;
/* 定义变量区*/
void input()
{
    memset(F,0,sizeof(F));
    memset(visit,0,sizeof(visit));
    ans=0;
    memset(MAP,0,sizeof(MAP));
    /*初始化区*/
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&m);
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&temp);    
            MAP[i][j]=temp;
            MAP[i][0]++;
        }
    }
    for(int i=1;i<=n;i++)
    scanf("%d",&wei[i]); 
}
void dfs(int pos,int deep)
{
    int OK=0;
    int t1=0,t2=0,I;
    for(int i=1;i<=MAP[pos][0];i++)
    {
        if(!visit[MAP[pos][i]])
        { 
        OK=1;
        visit[MAP[pos][i]]=1;
        dfs(MAP[pos][i],deep+1); 
        } 
    }
    if(OK)
    {
    F[deep][0][0]=max(F[deep+1][0][0],F[deep+1][1][0]);
    F[deep][1][0]=F[deep+1][0][0]+wei[pos];
    }
    else
    {
    F[deep][0][0]=0;
    F[deep][1][0]=wei[pos];
    }
}
void init()
{
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);
}
void dfs2(int pos,int deep)
{
    int OK=0;
    int t1=0,t2=0,I;
    for(int i=1;i<=MAP[pos][0];i++)
    {
        if(!visit[MAP[pos][i]])
        { 
        OK=1;
        visit[MAP[pos][i]]=1;
        dfs2(MAP[pos][i],deep+1); 
        break;
        } 
    }
    if(OK)
    {
    F[deep][0][0]=max(F[deep+1][0][0],F[deep+1][1][0]);
    F[deep][1][0]=F[deep+1][0][0]+wei[pos];
    F[deep][0][1]=max(F[deep+1][0][1],F[deep+1][1][1]);
    F[deep][1][1]=F[deep+1][0][1]+wei[pos];
    }
    else
    {
    F[deep][0][0]=0;
    F[deep][1][0]=-2100000000;
    F[deep][0][1]=0;
    F[deep][1][1]=wei[pos];
    }
}
int main()
{
//    init();
    int T;
    cin>>T;
    while(T--)
    {
        input();
        for(int i=1;i<=n;i++)
        { 
        if(MAP[i][0]==1&&visit[i]==0)
        {
            visit[i]=1;
            dfs(i,1);
            ans+=max(F[1][0][0],F[1][1][0]); 
            memset(F,0,sizeof(F));
        }
        }
        for(int i=1;i<=n;i++)
        {
        if(visit[i]==0)
        {
            visit[i]=1;
            dfs2(i,1);
            F[1][0][0]=max(F[1][0][0],F[1][1][0]);
            F[1][0][0]=max(F[1][0][0],F[1][0][1]);
            ans+=F[1][0][0];
            memset(F,0,sizeof(F));
        }
        } 
        cout<<ans<<endl;
    } 
    return 0;
}

在dfs的末尾给F赋初值

并且在dfs之后更新F即可