【BZOJ3935】Rbtree 树形DP

2022-01-13 08:43:47

【BZOJ3935】Rbtree

Description

给定一颗 N 个点的树，树上的每个点或者是红色，或者是黑色。

每个单位时间内，你可以任选两个点，交换它们的颜色。

出于某种恶趣味，你希望用最少的时间调整结点的颜色，使得对于每个点，离它最近的黑色点与它的距离不超过 x。

Input

输入的第一行包含整数 N 和 x(1 <= x <= 10^9)。

接下来一行 N 个整数 C1-Cn，表示结点的初始颜色。1 表示黑色，0 表示红色。

接下来 N-1 行，每行 3 个整数 ui, vi,wi(1 <= wi <= 10^9)，表示点 ui 和 vi 之间存在权值为 wi的边。

Output

输出一个数表示答案；如果无解，输出 “-1”。

Sample Input

3 2
1 0 0
1 2 2
2 3 2

Sample Output

HINT

数据规模和约定

对于100%的数据 N<=500

题解：大神们写的都是单纯形？算了我只知道树形DP。

本题的思路和小奇挖矿相同。用f[x][a][b]表示在x的子树中放a个黑点，且距离x最近的黑点是b的最小花费（即有多少点从白点变成黑点）。转移时，对于a那维相当于树形背包，我们考虑b那维怎么转移。

如果我们想用f[y][..][c]来更新f[x][..][b]，那么讨论：如果b==c，直接转移即可；如果c在y的子树中，那么用f[y][..][c]的最大值来更新f[x][..][b]即可；如果c不在y的子树中，那么我们将b换成c或者将c换成b一定不会变的更差，所以：不用转移！

#include <cstdio>

#include <cstring>

#include <iostream>

using namespace std;

typedef long long ll;

int n,m,ans,cnt;

ll K;

int v[505],p[505],q[505],Q[505],siz[505],g[505][505],to[1010],next[1010],head[505];

int f[505][505][505];

ll dis[505][505],val[1010];

inline int rd()

{

	int ret=0,f=1;	char gc=getchar();

	while(gc<'0'||gc>'9')	{if(gc=='-')	f=-f;	gc=getchar();}

	while(gc>='0'&&gc<='9')	ret=ret*10+(gc^'0'),gc=getchar();

	return ret*f;

}

inline void add(int a,int b,int c)

{

	to[cnt]=b,val[cnt]=c,next[cnt]=head[a],head[a]=cnt++;

}

void dfs1(int x,int fa,int y)

{

	if(y==1)	p[x]=++p[0],Q[p[0]]=x;

	for(int i=head[x];i!=-1;i=next[i])	if(to[i]!=fa)	dis[to[i]][y]=dis[x][y]+val[i],dfs1(to[i],x,y);

	if(y==1)	q[x]=p[0];

}

void dfs2(int x,int fa)

{

	int i,y,j,k,a,mn;

	siz[x]=1;

	for(a=1;a<=n;a++)	if(a!=x&&dis[a][x]<=K)	f[x][0][a]=0;

	f[x][1][x]=!v[x];

	for(i=head[x];i!=-1;i=next[i])	if(to[i]!=fa)

	{

		y=to[i],dfs2(y,x);

		memset(g,0x3f,sizeof(g));

		for(j=0;j<=siz[x]&&j<=m;j++)	for(k=0;k<=siz[y]&&j+k<=m;k++)

		{

			mn=0x3f3f3f3f;

			for(a=p[y];a<=q[y];a++)	mn=min(mn,f[y][k][Q[a]]);

			for(a=1;a<=n;a++)	g[j+k][a]=min(g[j+k][a],f[x][j][a]+f[y][k][a]);

			for(a=1;a<p[y];a++)	g[j+k][Q[a]]=min(g[j+k][Q[a]],f[x][j][Q[a]]+mn);

			for(a=q[y]+1;a<=n;a++)	g[j+k][Q[a]]=min(g[j+k][Q[a]],f[x][j][Q[a]]+mn);

		}

		siz[x]+=siz[y];

		for(j=0;j<=siz[x]&&j<=m;j++)	for(a=1;a<=n;a++)	f[x][j][a]=g[j][a];

	}

}

int main()

{

	n=rd(),K=rd();

	int i,a,b,c;

	memset(head,-1,sizeof(head));

	for(i=1;i<=n;i++)	v[i]=rd(),m+=v[i];

	for(i=1;i<n;i++)	a=rd(),b=rd(),c=rd(),add(a,b,c),add(b,a,c);

	for(i=1;i<=n;i++)	dfs1(i,0,i);

	memset(f,0x3f,sizeof(f));

	dfs2(1,0);

	ans=1<<30;

	for(i=1;i<=n;i++)	ans=min(ans,f[1][m][i]);

	printf("%d",ans>n?-1:ans);

	return 0;

}

码农公寓