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的战斗力\(A_{i}\)。

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

Hint

输入数据保证\(4 \le n \le 100000\)，\(1 \le a,b \le n\)，\(1 \le m \le 200000\)，\(-1000 \le Ai \le 1000\)。

同BZOJ 1040。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

using namespace std;

#define inf (1<<30)

#define maxn 200010

int n,m,cnt,cir[maxn],w[maxn],fa[maxn],side[maxn];

int dfn[maxn],low[maxn],toit[maxn*2],next[maxn*2];

int f[maxn][2],g[maxn][2],ans;

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;

}

inline void add(int a,int b) { next[++cnt] = side[a]; toit[cnt] = b; side[a] = cnt; } 

inline void ins(int a,int b) { add(a,b); add(b,a); }

inline void dp(int root,int last)

{

	int nn = 0;

	while (last != root) cir[++nn] = last,last = fa[last];

	cir[++nn] = root;

	for (int i = 1;i <= nn;++i) g[cir[i]][0] = f[cir[i]][0],g[cir[i]][1] = f[cir[i]][1];

	g[root][1] = inf;

	for (int i = nn-1;i;--i)

	{

		g[cir[i]][0] += min(g[cir[i+1]][0],g[cir[i+1]][1]);

		g[cir[i]][1] += g[cir[i+1]][0];

	}

	f[root][0] = min(g[cir[1]][0],g[cir[1]][1]);

	for (int i = 1;i <= nn;++i) g[cir[i]][0] = f[cir[i]][0],g[cir[i]][1] = f[cir[i]][1];

	g[root][0] = inf;

	for (int i = nn-1;i;--i)

	{

		g[cir[i]][0] += min(g[cir[i+1]][0],g[cir[i+1]][1]);

		g[cir[i]][1] += g[cir[i+1]][0];

	}

	f[root][1] = g[cir[1]][0];

}

inline void dfs(int now)

{

	dfn[now] = low[now] = ++cnt;

	f[now][0] = w[now];

	for (int i = side[now];i;i = next[i])

		if (toit[i] != fa[now])

		{

			if (fa[toit[i]] == now) continue;

			if (!dfn[toit[i]]) fa[toit[i]] = now,dfs(toit[i]);

			low[now] = min(low[now],low[toit[i]]);

			if (low[toit[i]] > dfn[now])

			{

				f[now][0] += min(f[toit[i]][0],f[toit[i]][1]);

				f[now][1] += f[toit[i]][0];

			}

		}

	for (int i = side[now];i;i = next[i])

		if (toit[i] != fa[now] && dfn[toit[i]] > dfn[now] && fa[toit[i]] != now)

			dp(now,toit[i]);

}

int main()

{

	freopen("1487.in","r",stdin);

	freopen("1487.out","w",stdout);

	n = read(); m = read();

	for (int i = 1;i <= m;++i) ins(read(),read());

	for (int i = 1;i <= n;++i) w[i] =read(),ans += w[i];

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

		if (!dfn[i]) cnt = 0,dfs(i),ans -= min(f[i][0],f[i][1]);

	printf("%d",ans);

	fclose(stdin); fclose(stdout);

	return 0;

}

巴特西

BZOJ 1487 无归岛

Description

Input

Output

Sample Input

Sample Output

Hint

最新文章

热门文章