P2458 [SDOI2006]保安站岗

标签：站岗 6001 int back P2458 SDOI2006 DP

#include<bits/stdc++.h>
using namespace std;
class DP_on_tree{
public:
	int n;
	int f[6001][3];
	vector < int > e[6001];
	void DP(int x,int fa)
	{
		f[x][0]=f[x][2]=0;
		int sum=0x3f3f3f3f;
		for(int i=0; i<e[x].size(); i++)
		{
			int y=e[x][i];
			if(y==fa)continue;
			DP(y,x);
			f[x][1]+=min(f[y][0],min(f[y][1],f[y][2]));
			f[x][2]+=min(f[y][0],f[y][1]);
			f[x][0]+=min(f[y][0],f[y][1]);
			sum=min(sum,f[y][1]-min(f[y][0],f[y][1]));
		}
		f[x][0]+=sum;
		return;
	}
	void Main()
	{
		scanf("%d",&n);
		int x;
		for(int i=1; i<=n; i++)
		{
			cin>>x;
			int k;cin>>k;
			f[x][1]=k;
			cin>>k;
			for(int j=1,y; j<=k; j++)
			{
				cin>>y;
				e[x].push_back(y);
				e[y].push_back(x);
			}
		}
		DP(1,-1);
		printf("%d\n",min(f[1][0],f[1][1]));
	}
};
int main()
{
	DP_on_tree x;
	x.Main();
}

标签：站岗,6001,int,back,P2458,SDOI2006,DP
From： https://www.cnblogs.com/dadidididi/p/16746970.html