「BZOJ1487」[HNOI2009] 无归岛
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
1 2
2 3
3 4
4 1
3 6
3 5
5 6
20 10 30 15 20 10
Sample Output
「样例说明」
有四个岛，生物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的取舍
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 |
#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #include<cmath> #include<cstring> #define inf 2000000000 #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,ind,cnt; int f[100005],g[100005],mx[100005]; int dfn[100005],q[100005],fa[100005]; int last[100005],val[100005]; int a[100005]; bool mark[100005]; struct edge{ int to,next; }e[400005]; void insert(int u,int v) { e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt; e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt; } void dp(int rt,int x) { int u0=0,u1=0,v0,v1; for(int j=x;j!=rt;j=fa[j]) { v1=u0+f[j];v0=u1+g[j]; u0=v0;u1=max(v0,v1); } g[rt]+=u1; u0=-inf;u1=0; for(int j=x;j!=rt;j=fa[j]) { v1=u0+f[j];v0=u1+g[j]; u0=v0;u1=max(v0,v1); } f[rt]+=u0; } void dfs(int x) { dfn[x]=++ind; for(int i=last[x];i;i=e[i].next) if(!dfn[e[i].to]) { fa[e[i].to]=x; dfs(e[i].to); } f[x]=val[x]; for(int i=last[x];i;i=e[i].next) if(dfn[e[i].to]>dfn[x]&&fa[e[i].to]!=x) dp(x,e[i].to); } int main() { n=read();m=read(); for(int i=1;i<=m;i++) { int u=read(),v=read(); insert(u,v); } for(int i=1;i<=n;i++)val[i]=read(); dfs(1); printf("%d",max(f[1],g[1])); return 0; } |
OI 课件=>
这种做法不会很慢么。。每找到一个环上的点都要遍历环一遍？
一个环应该只遍历一次233
哦对，我SB。。。