「BZOJ1487」[HNOI2009] 无归岛

2014年12月12日4,3103

Description

Neverland是个神奇的地方,它由一些岛屿环形排列组成,每个岛上都生活着之中与众不同的物种。但是这些物种都有一个共同的生活习性:对于同一个岛上的任意两个生物,他们有且仅有一个公共朋友,即对同一岛上的任意两个生物a和b有且仅有一个生物c既是a的朋友也是b的朋友,当然某些岛上也可能会只有一个生物孤单地生活着。这一习性有一个明显的好处,当两个生物发生矛盾的时候,他们可以请那个唯一的公共朋友来裁决谁对谁错。

另外,岛与岛之间也有交流,具体来说,每个岛都会挑选出一个最聪明的生物做代表,然后这个生物与他相邻的两个岛的代表成为朋友。

不行的是,A世界准备入侵Neverland,作为Neverland的守护者,Lostmonkey想知道在一种比较坏的情况下Never的战斗力。因为和朋友并肩作战,能力会得到提升,所以Lostmonkey想知道在不选出一对朋友的情况下Neverland的最大战斗力。即选出一些生物,且没有一对生物是朋友,并且要求它们的战斗力之和最大。

Input

第一行包含用空格隔开的两个整数n和m,分别表示Neverland的生物种数和朋友对数。接下来的m行描述所有朋友对,具体来说,每行包含用空格隔开的两个整数a和b,表示生物a和生物b是朋友(每对朋友只出现一次)。第m+2行包含用空格隔开的n个整数,其中第i个整数表示生物i的战斗力Ai。输入数据保证4<=n<=100000,1<=a,b<=n,1<=m<=200000,-1000<=Ai<=1000.

Output

仅包含一个整数,表示满足条件的最大战斗力。

Sample Input

6 7
1 2
2 3
3 4
4 1
3 6
3 5
5 6
20 10 30 15 20 10

Sample Output

50
「样例说明」
有四个岛,生物1在1号岛,生物2在2号岛,生物3、5、6在3号岛,生物4在4号岛。

HINT

NeverLand这个单词在“小飞侠彼得潘”中译为梦幻岛,在这却成为无归岛,真是汗啊.

题解

仙人掌图上dp好像还是没搞清楚

不过这道题比求直径要简单挺多TAT

用f[x],g[x]表示x选/不选时的最大价值

类似树形dp

f[x]=∑(g[son] + val[x])

g[x]=∑ (max( f[x],g[x] ))

但是环上需要一些技巧 T T 即一个环

… —— y — rt — x —— …

|                                |

……………………….

则rt不取时,rt两边只能最多取一个

分两次dp就比较方便处理了

代码还是很短的。。

u0,u1表示现在这个能/不能取,v1表示取的最大价值,v0表示不取的最大价值

则有

for x -> rt

v1=u0+f[j],v0=u1+g[j]

u0=v0,u1=max(v0,v1)

控制u0,u1的初值限制x的取舍

 

avatar
1 Comment threads
2 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
2 Comment authors
orzwzyhzwer Recent comment authors
  Subscribe  
提醒
orzwzy
orzwzy

这种做法不会很慢么。。每找到一个环上的点都要遍历环一遍?