程序设计在线评测(Online Judge)

2017年湖南科技大学大学生计算机程序设计竞赛初定于12月17日举行!有意参赛请加QQ群“湖科大程序设计校赛群(369699377)”

问题 1018. -- 2011市赛题:Game

1018: 2011市赛题:Game

时间限制: 1 Sec  内存限制: 128 MB
提交: 14  解决: 5
[提交][状态][讨论版]

题目描述

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

输入

第一行是caseT(1<=T<=100)

接下来有Tcase,每组casen + 2

第一行有一个整数n(1<= n<= 100) 表示有n个小朋友。

接下来n行,每行以整数k开始, 表示第i个小朋友有k个讨厌的人,接着k个数表示他讨厌的小朋友编号。(1 <= k <= 2) 如果i讨厌j,这必然也有j讨厌i

接下去一行有n个值,表示每个小朋友的快乐值。

输出

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

样例输入

1
3

1 2

2 1 3 

1 2

5 9 5

样例输出

10

提示

若a讨厌b,则ab间建一条边。从题目的限制中可以得知最后改图一定是一个简单路或者单环的集合。

对于简单路或者环。可以用dp求出最大值。

简单路的dp方程是

dp[i][0]表示第i个人不取,前i个人所得最大快乐值

dp[i][1]表示第i个人取,前i个人所得最大快乐值

dp[i][0] = max(dp[i-1][0], dp[i-1][1])

dp[i][1] = val[i] + dp[i-1][0]

环的情况类似。

来源

[提交][状态][讨论版]