1487: [HNOI2009]无归岛
Time Limit: 1 Sec Memory Limit: 64 MBSubmit: 253 Solved: 139
[Submit][Status]
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这个单词在“小飞侠彼得潘”中译为梦幻岛，在这却成为无归岛，真是汗啊.
orz让我讲仙人掌的K2CO3大爷
题目看了好久= =
大概是这样的吧：
有好多个岛
每个岛是由一些三角的环相连且任意2个三角形间没有公共边
然后每个岛任意选一个点，连起来
附个图吧。。。
红的圈里面是一个岛，绿色的是每个岛的代表。。
那么显然图满足仙人掌性质
额。。求一个点集满足任意2点间没有边，最大化点集的“战斗力”
就是说取了一个点那么相邻的不能取。。
如果是棵树那就是很水的树形dp对吧。。
记录f[x]表示选x的最大答案,g[x]表示不选x的最大答案
f[x]=data[x]+Σg[i](i是x的儿子)
g[x]=Σmax(g[i],f[i])(i是x的儿子)
然后转移
有环其实也差不多。。。。
答案记录在环中dfn值最小的那个点上(记为root)
然后从一个方向转移过去
记录u0,u1,v0,v1
u0,u1表示前一个点不选/选的答案
v0,v1表示当前点不选/选的答案
设当前点为i
v0=u1+g[i];v1=u0+f[i];
u0=max(v0,v1);u1=v0;
好像差不多就这样了。。。
代码
#include <cstdio>
#include <algorithm>
#define maxn 200005
using namespace std;
int a,b,c,d,e,h,i,j,k,l,m,n,tot;
int f[maxn],g[maxn],fa[maxn],dfn[maxn],way[maxn*2],next[maxn*2],last[maxn*2],data[maxn];
inline void make(int a,int b){
way[++tot]=b;next[tot]=last[a];last[a]=tot;
way[++tot]=a;next[tot]=last[b];last[b]=tot;
}
inline void dp(int root,int x){
int u0,u1,v0,v1;
u0=0;u1=0;
for(int i=x;i!=root;i=fa[i]){
v0=u1+g[i];v1=u0+f[i];
u0=v0;u1=max(v0,v1);
}
g[root]+=u1;
u0=-1<<30;u1=0;
for(int i=x;i!=root;i=fa[i]){
v0=u1+g[i];v1=u0+f[i];
u0=v0;u1=max(v0,v1);
}
f[root]+=u0;
}
void dfs(int x){
dfn[x]=++k;
for(int i=last[x];i;i=next[i])if(!dfn[way[i]]){
fa[way[i]]=x;
dfs(way[i]);
}
f[x]=data[x];
for(int i=last[x];i;i=next[i])
if(dfn[way[i]]>dfn[x]&&fa[way[i]]!=x){
dp(x,way[i]);
}
}
int main(){
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++){
scanf("%d%d",&a,&b);
make(a,b);
}
for(i=1;i<=n;i++)scanf("%d",&data[i]);
dfs(1);
printf("%d",max(f[1],g[1]));
return 0;
}
评论 (0)
