[poj2152]fire_树形dp

fire poj-2152

　　　　题目大意：给出一颗树，给出两个相邻节点的距离，以及每个节点的接受范围，还有当前节点的代价。我们想要求出覆盖整个图的最小代价。

　　　　注释：一个点被覆盖，当且仅当该点有防火站或者这个点的接受范围之内有防火站。计算两个不相邻节点的距离用LCA计算。节点数<=1000，接受范围<=10,000.

　　　　　　想法：poj最后一道树形dp，用这道神一样的树形dp结尾，在好不过。

　　　　　　对于一个节点来讲设几个状态：ans[pos]表示使以pos为根的子树被保护的最小代价。dp[pos][save]表示以pos为根的子树被保护的最小代价且pos节点必须被save节点保护。dist[i][j]表示i到j的距离。cost[i]表示在该节点建立防火站的代价。d[i]表示该节点的接受范围。

　　　　　　然后，我们考虑神奇的转移：$dp[u][v]=cost[v]+\sum min(dp[k][v]-cost[v],ans[k])$。这个状态的充要条件是k也可以被v覆盖。如果不然，我们就直接将dp[u][v]+=ans[k]。

　　　　最后，附上丑陋的代码... ...

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#define N 2100
using namespace std;
const int inf=1e9;
int cost[N],d[N],n;
int dist[N][N];
int val[N];
int dp[N][N];
int head[N];
int ans[N];
int to[N];
int nxt[N];
int tot;
queue<int>q;
inline void add(int x,int y,int z)
{
	to[++tot]=y;
	val[tot]=z;
	nxt[tot]=head[x];
	head[x]=tot;
}
void get_dist(int dist[],int s)
{
	dist[s]=0;
	q.push(s);
	while(q.size())
	{
		int u=q.front(); q.pop();
		for(int i=head[u];i;i=nxt[i])
		{
			int v=to[i];
			if(!dist[v]&&v!=s)
			{
				dist[v]=dist[u]+val[i];
				q.push(v);
			}
		}
	}
}
void dfs(int pos,int fa)
{
	for(int i=head[pos];i;i=nxt[i])
	{
		if(to[i]==fa) continue;
		dfs(to[i],pos);
	}
	for(int v=1;v<=n;v++)
	{
		if(dist[pos][v]<=d[pos])
		{
			int temp=0;
			for(int i=head[pos];i;i=nxt[i])
			{
				int k=to[i];
				if(k==fa) continue;
				temp+=min(dp[k][v]-cost[v],ans[k]);
			}
			dp[pos][v]=cost[v]+temp;
		}
		else dp[pos][v]=inf;
	}
	for(int i=1;i<=n;i++)
	{
		ans[pos]=min(ans[pos],dp[pos][i]);
	}
}
inline void original()
{
	tot=0;
	memset(head,0,sizeof head);
	memset(dp,0,sizeof dp);
	memset(dist,0,sizeof dist);
	memset(ans,63,sizeof ans);
}
int main()
{
	int cases;
	scanf("%d",&cases);
	while(cases--)
	{
		original();
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&cost[i]);
		}
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&d[i]);
		}
		int a,b,c;
		for(int i=1;i<n;i++)
		{
			scanf("%d%d%d",&a,&b,&c);
			add(a,b,c);
			add(b,a,c);
		}
		for(int i=1;i<=n;i++)
		{
			get_dist(dist[i],i);
		}
		dfs(1,0);
		printf("%d\n",ans[1]);
	}
	return 0;
}

　　　　小结：太tm神了。其中，计算节点距离的处理是很巧妙地... ...

巴特西

[poj2152]fire_树形dp

最新文章

热门文章