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

【样例说明】

有四个岛，生物1在1号岛，生物2在2号岛，生物3、5、6在3号岛，生物4在4号岛。

HINT

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

Solution

题目描述好奇怪啊

就是要求仙人掌的最大点权独立集

将环和树的分开dp

如果是一个树，那么就是个入门dp，\(f_{u,0/1}\) 代表 \(u\) 这个点选或不选的最优答案，转移很简单

对于一个环，把环上的点拿出来，找任意一条边，强制这条边的一端不选，线性dp一下，再强制另一段不选，线性dp一下，将两次dp的答案取最大更新到 \(root\) 就好了

#include<bits/stdc++.h>

#define ui unsigned int

#define ll long long

#define db double

#define ld long double

#define ull unsigned long long

const int MAXN=100000+10,MAXM=200000+10,inf=0x3f3f3f3f;

int n,m,val[MAXN],beg[MAXN],nex[MAXM<<1],to[MAXM<<1],DFN[MAXN],LOW[MAXN],Visit_Num,e,f[MAXN][2],g[MAXN][2],ex[2],fa[MAXN],cnt,a[MAXN],ans;

template<typename T> inline void read(T &x)

{

	T data=0,w=1;

	char ch=0;

	while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();

	if(ch=='-')w=-1,ch=getchar();

	while(ch>='0'&&ch<='9')data=((T)data<<3)+((T)data<<1)+(ch^'0'),ch=getchar();

	x=data*w;

}

template<typename T> inline void write(T x,char ch='\0')

{

	if(x<0)putchar('-'),x=-x;

	if(x>9)write(x/10);

	putchar(x%10+'0');

	if(ch!='\0')putchar(ch);

}

template<typename T> inline void chkmin(T &x,T y){x=(y<x?y:x);}

template<typename T> inline void chkmax(T &x,T y){x=(y>x?y:x);}

template<typename T> inline T min(T x,T y){return x<y?x:y;}

template<typename T> inline T max(T x,T y){return x>y?x:y;}

inline void insert(int x,int y)

{

	to[++e]=y;

	nex[e]=beg[x];

	beg[x]=e;

}

inline void loop(int root,int x)

{

	a[cnt=1]=x;

	for(register int i=x;i!=root;i=fa[i])a[++cnt]=fa[i];

	g[x][0]=f[x][0],g[x][1]=-inf;

	for(register int i=2;i<=cnt;++i)

	{

		g[a[i]][0]=f[a[i]][0]+max(g[a[i-1]][0],g[a[i-1]][1]);

		g[a[i]][1]=f[a[i]][1]+g[a[i-1]][0];

	}

	ex[0]=g[root][0],ex[1]=g[root][1];

	g[x][0]=f[x][0],g[x][1]=f[x][1];

	for(register int i=2;i<=cnt;++i)

	{

		g[a[i]][0]=f[a[i]][0]+max(g[a[i-1]][0],g[a[i-1]][1]);

		g[a[i]][1]=f[a[i]][1]+g[a[i-1]][0];

	}

	chkmax(ex[0],g[root][0]);

	f[root][0]=ex[0],f[root][1]=ex[1];

}

inline void Tarjan(int x,int p)

{

	DFN[x]=LOW[x]=++Visit_Num;fa[x]=p;

	f[x][0]=0,f[x][1]=val[x];

	for(register int i=beg[x];i;i=nex[i])

		if(to[i]==p)continue;

		else if(!DFN[to[i]])

		{

			Tarjan(to[i],x);

			chkmin(LOW[x],LOW[to[i]]);

			if(LOW[to[i]]>DFN[x])

			{

				f[x][0]+=max(f[to[i]][1],f[to[i]][0]);

				f[x][1]+=f[to[i]][0];

			}

		}

		else if(DFN[to[i]]<DFN[x])chkmin(LOW[x],DFN[to[i]]);

	for(register int i=beg[x];i;i=nex[i])

		if(to[i]==p)continue;

		else if(fa[to[i]]!=x&&DFN[to[i]]>DFN[x]&&LOW[to[i]]<=DFN[x])loop(x,to[i]);

}

int main()

{

	read(n);read(m);

	for(register int i=1;i<=m;++i)

	{

		int u,v;read(u);read(v);

		insert(u,v);insert(v,u);

	}

	for(register int i=1;i<=n;++i)read(val[i]);

	for(register int i=1;i<=n;++i)

		if(!DFN[i])Tarjan(i,0),ans+=max(f[i][0],f[i][1]);

	printf("%d\n",ans);

	return 0;

}

巴特西

【刷题】BZOJ 1487 [HNOI2009]无归岛