程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> poj1155 TELE（樹形dp+背包）

poj1155 TELE（樹形dp+背包）

編輯：關於C++

TELE Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 4344 Accepted: 2352

Description

A TV-network plans to broadcast an important football match. Their network of transmitters and users can be represented as a tree. The root of the tree is a transmitter that emits the football match, the leaves of the tree are the potential users and other vertices in the tree are relays (transmitters).
The price of transmission of a signal from one transmitter to another or to the user is given. A price of the entire broadcast is the sum of prices of all individual signal transmissions.
Every user is ready to pay a certain amount of money to watch the match and the TV-network then decides whether or not to provide the user with the signal.
Write a program that will find the maximal number of users able to watch the match so that the TV-network's doesn't lose money from broadcasting the match.

Input

The first line of the input file contains two integers N and M, 2 <= N <= 3000, 1 <= M <= N-1, the number of vertices in the tree and the number of potential users.
The root of the tree is marked with the number 1, while other transmitters are numbered 2 to N-M and potential users are numbered N-M+1 to N.
The following N-M lines contain data about the transmitters in the following form:
K A1 C1 A2 C2 ... AK CK
Means that a transmitter transmits the signal to K transmitters or users, every one of them described by the pair of numbers A and C, the transmitter or user's number and the cost of transmitting the signal to them.
The last line contains the data about users, containing M integers representing respectively the price every one of them is willing to pay to watch the match.

Output

The first and the only line of the output file should contain the maximal number of users described in the above text.

Sample Input

9 6
3 2 2 3 2 9 3
2 4 2 5 2
3 6 2 7 2 8 2
4 3 3 3 1 1

Sample Output

Source

Croatia OI 2002 Final Exam - Second Day
題意：給定一棵樹，1為根結點表示電視台，有m個葉子節點表示客戶，有n-m-1個中間節點表示中轉站，每條樹邊有權值。現在要在電視台播放一場比賽，每個客戶願意花費cost[i]的錢觀看，而從電視台到每個客戶也都有個費用，並且經過一條邊只會產生一個費用。問電視台不虧損的情況最多有幾個客戶可以看到比賽分析：本題在思考的時候可分兩種情況：1、當節點為葉子節點時，每個用戶都要支付Money，那當前選一個的價值為Money值，中轉站和電視台要計算的是在保證不虧損也就是從用戶那獲得得價值減去中轉費用必須大等於0，那麼葉子節點的Money值就是基本信息。2、當節點為中轉站或者非葉子節點時，每次從子節點中選擇n個並計算收取的Money和中轉費用，如果兩者想減大等於0就用n來更新答案。怎麼轉換到分組背包呢？可以這樣想，每次從每個子節點中都只能取若干個，不可能重疊著取，那幾個節點就是幾組背包，最大容量是這點的葉子子孫數量，選幾個節點就是選擇的容量，價值就是用戶給的Money-中轉費用。

#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#include 
#include 
using namespace std;
const double eps = 1e-6;
const double pi = acos(-1.0);
const int INF = 0x3f3f3f3f;
const int MOD = 1000000007;
#define ll long long
#define CL(a,b) memset(a,b,sizeof(a))
#define MAXN 3010

int n,m,pre;
int money[MAXN],dp[MAXN][MAXN];//money表示每條權的權值
int ans,sum[MAXN],vis[MAXN];//sum表示每個結點的最優解，vis標記

struct node
{
    int v,len;//len為權值
    node *next;
}*head[MAXN*2], tree[MAXN*2];

void add(int x, int y, int len)
{
    tree[pre].v = y, tree[pre].len = len;
    tree[pre].next = head[x], head[x] = &tree[pre++];
    tree[pre].v = x, tree[pre].len = len;
    tree[pre].next = head[y], head[y] = &tree[pre++];
}

void dfs(int v, int len)
{
    if (vis[v]) return ;
    vis[v] = 1, dp[v][0] = 0;
    int tot = 0;
    node *p = head[v];
    while(p != NULL)
    {
        if(!vis[p->v])
        {
            tot++;
            dfs(p->v, len);
            sum[v] += sum[p->v];
        }
        p = p->next;
    }
    if(tot == 0)//根結點
    {
        sum[v] = 1;
        dp[v][1] = money[v]-len;
    }
    else
    {
        p = head[v];
        while(p != NULL)
        {
            int k=p->v, len=p->len;
            for(int j=sum[v]; j>=1; j--)//背包求解
            {
                for(int i=1; i<=sum[k]; i++)
                {
                    if (j >= i&&dp[v][j-i]!=-INF&&dp[k][i]!=-INF)
                        dp[v][j] = max(dp[v][j], dp[v][j-i]+dp[k][i]-len);
                }
            }
            p = p->next;
        }
    }
}

int main()
{
    int a,b,k;
    while(cin>>n>>m)
    {
        pre=1; ans=-INF;
        CL(vis, 0);
        CL(sum, 0);
        CL(head, NULL);
        for(int i=0; i<=n; i++)
            for(int j=0; j<=n; j++)
            dp[i][j]=-INF;
        for(int i=1; i<=n-m; i++)
        {
            cin>>k;
            for(int j=1; j<=k; j++)
            {
                cin>>a>>b;
                add(i, a, b);
            }
        }
        for (int i=n-m+1; i<=n; i++)
            cin>>money[i];
        dfs(1, 0);
        for(int i=n; i>=0; i--)
            if(dp[1][i] >= 0){cout<