A simple Blog for wyx I've been down the bottle hoping.
POJ 1155 TELE
发表于: | 分类: Oi | 评论:0 | 阅读:104

给定一棵树,在树的叶子节点有权值,走过任意一条边有边权,1号点为根节点,求在和$>=0$的前提下,最多从$root$经过多少个点
经典的树形$dp$
记录一下每个点下面有多少个孩子,然后每次背包一下就行了
注意多组数据的初始化,还有,在转移的时候注意是用原数组转移还是用已经转移过的转移,不同的写法不一样需要自己分析

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#define N 3000+5
#define M 6000+5
const int inf = -0x7fffff;
using namespace std;

int head[N];
int num[N];

struct graph
{
    int next,to,val;
    graph () {}
    graph (int _next,int _to,int _val)
    :next(_next),to(_to),val(_val){}
}edge[M];

int cnt;

inline void add(int x,int y,int z)
{
    edge[++cnt] = graph(head[x],y,z);
    head[x] = cnt;
}

inline int read()
{
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

int f[N][N];
int tmp[N]; 

void init()
{
    memset(head,0,sizeof head);
    memset(num,0,sizeof num);
    memset(tmp,0,sizeof tmp);
    cnt = 0;
}

void DFS(int x)
{
    for(int i=head[x];i;i=edge[i].next)
    {
        DFS(edge[i].to);
        for(int j=0;j<=num[x];++j)
            tmp[j] = f[x][j];
        for(int j=0;j<=num[x];++j)
            for(int k=1;k<=num[edge[i].to];++k)
                f[x][j+k] = max(f[x][j+k],tmp[j]+f[edge[i].to][k]-edge[i].val);
        num[x]  += num[edge[i].to];
    }
}

int main()
{
    int n , m;
    //freopen("13.in","r",stdin);
    while(cin >> n >> m)
    {
        init();
        for(int i=1;i<=n;++i)
            for(int j=1;j<=m;++j)
                f[i][j] = inf;
        for(int i=1;i<=n-m;++i)
        {
            int k = read();
            num[i] = 0;
            for(int j=1;j<=k;++j)
            {
                int y = read() , z = read();
                add(i,y,z);
            }
        }
        for(int i=n-m+1;i<=n;++i)
            num[i] = 1,f[i][1] = read();
        DFS(1);
        for(int i=m;i>=0;--i)if(f[1][i]>=0){printf("%d\n",i);break;}
    }
}

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP