POJ1155 TELE(树DP)

63 阅读 0 评论 42 点赞

我是靠谱客的博主柔弱吐司，最近开发中收集的这篇文章主要介绍POJ1155 TELE(树DP)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目：

poj.org/problem?id=1155

题意：

有N个节点的一棵树，上面前n-m个节点是信号站，后m个节点是用户，每个节点之间传输有消耗，每个用户有费用，总信号从1节点传输出来，求在不赔本的情况下能够最多传输给多少个用户。

思路：

明显是树DP，考虑3000个节点，dp[i][j]就是第i个节点在传输给j个用户的情况下的最小花费是多少，记录每个节点取得的可能最大用户数目，然后对于每个子节点暴力枚举更新就行了，最后1节点时花费为非正的最大的用户数就是答案。

注意每次更新一个节点的子节点时要把当前DP值储存下来用于更新，否则枚举不同数目时可能会重复。

代码：

//kopyh
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define MOD 1000000007
#define N 3001
using namespace std;
int n,m,sum,res,flag;
int dp[N][N],val[N],num[N],vis[N],tmp[N];
vector<int>g[N],f[N];
void dfs(int now)
{
    dp[now][0] = 0;
    if(val[now]>=0)dp[now][1] = -val[now], num[now]=1;
    fo