【BZOJ1040】骑士（动态规划）

题面

题解

对于每一组厌恶的关系

显然是连边操作

如果是一棵树的话

很显然的树型\(dp\)

但是，现在相当于有很多个基环

也就是在一棵树的基础上再加了一条边

这个时候怎么办，

暴力拆掉基环（拆掉任意一条边）

跑两遍\(dp\)

计算出强制不选两个点中某一个的最大值

此时就是这个基环的最大值

（不用拆掉所有的边，因为只要拆掉一条边之后可以用树型\(dp\)来控制）

可能存在多个联通块

所以要算多遍，然后求和

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define MAX 1200000

inline int read()

{

	int x=0,t=1;char ch=getchar();

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

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

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return x*t;

}

struct Line{int v,next;}e[MAX<<1];

int h[MAX],cnt=2;

int n,a[MAX];

inline void Add(int u,int v){e[cnt]=(Line){v,h[u]};h[u]=cnt++;}

long long f[MAX][2];

int U,V,L;

int fa[MAX],Cri[MAX],tot;

int getf(int x){return x==fa[x]?x:fa[x]=getf(fa[x]);}

void dfs(int u,int ff)

{

	f[u][1]=a[u];f[u][0]=0;

	for(int i=h[u];i;i=e[i].next)

	{

		if(i==L||i==(L^1))continue;

		int v=e[i].v;

		if(v==ff)continue;

		dfs(v,u);

		f[u][0]+=max(f[v][0],f[v][1]);

		f[u][1]+=f[v][0];

	}

}

int main()

{

	n=read();

	for(int i=1;i<=n;++i)fa[i]=i;

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

	{

		a[i]=read(),u=read();Add(u,i),Add(i,u);

		if(getf(u)!=getf(i))fa[getf(u)]=getf(i);

		else Cri[++tot]=cnt-1;

	}

	long long ans=0;

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

	{

		long long ss=0;

		U=e[Cri[i]].v;V=e[Cri[i]^1].v;

		L=Cri[i];

		dfs(U,0);ss=max(ss,f[U][0]);

		dfs(V,0);ss=max(ss,f[V][0]);

		ans+=ss;

	}

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

	return 0;

}

巴特西

【BZOJ1040】骑士（动态规划）

【BZOJ1040】骑士（动态规划）

题面

题解

最新文章

热门文章