【未完】DOJ-Z1012 皇宫看守

这题可以看做[洛谷P2016 战略游戏](https://www.luogu.com.cn/problem/P2016)的进阶版，多了一个价值

~~如果一道题不够难，那就把它放到树上。~~

**题意**

给出一棵树，每个结点都可以看守与其连接的点。在每个点上安排看守需要花费一定的代价，每个点的代价各不相同。求在能够看守到每一个点的情况下的最少花费。

**思路**

树状dp。设 $f[i][0/1/2]$ 表示当前结点由父亲/儿子/自己看守。

**实现**

```cpp
#include <bits/stdc++.h>
using namespace std;
int n,f[2005][3],bk[2005],k[2005],head[2005],cnt,ans=1;
struct node{
	int v,next;
}e[2005];
void add(int u,int v)
{ //链式前向星
	cnt++;
	e[cnt].v=v;
	e[cnt].next=head[u];
	head[u]=cnt;
}
void dfs(int u)
{
	f[u][0]=0; //父 
	f[u][1]=1e9; //子 
	f[u][2]=k[u]; //己 
	for (int i=head[u];i>0;i=e[i].next)
	{
		int j=e[i].v;
		dfs(j);
		f[u][0]+=min(f[j][1],f[j][2]);
		f[u][2]+=min(f[j][0],min(f[j][1],f[j][2])); 
	}
	for (int i=head[u];i>0;i=e[i].next)
	{
		int j=e[i].v;
		f[u][1]=min(f[u][1],f[u][0]+f[j][2]-min(f[j][1],f[j][2]));
	}
}
signed main()
{
	cin>>n;
	for (int i=1;i<=n;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		k[u]=v;//把代价存到点上 
		while (w--)
		{//输入所连接的点 
			int r;
			cin>>r;
			add(u,r);
			bk[r]=true; //当时bk打成了k，跟while上面的转移代价冲突了，导致WA
		}
	}
	while (bk[ans]==true) ans++;
	dfs(ans);
	cout<<min(f[ans][1],f[ans][2]);
	return 0;
}
```

正在渲染内容...