A simple Blog for wyx I've been down the bottle hoping.
POJ 1947 Rebuilding Roads 树形dp
发表于: | 分类: Oi | 评论:0 | 阅读:122

这题还是挺经典的
简单说一下思路和一些需要注意的细节
用$f(i,j)$表示在以$i$为根的子树中选择$k$个连续的点的最小花费
$f(i,j) = min(f(i,k)+f(son,j-k))$
需要注意的是统计答案的时候
除了根节点,剩下的都得+1统计,因为需要断掉和父亲的连边
然而开始的时候我都是+1统计的,结果调样例调了半个小时,怎么调都得3 zz

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

int head[N];

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

int cnt;

inline void add(int x,int y)
{
    edge[++cnt] = graph(head[x],y);
    head[x] = cnt;
    edge[++cnt] = graph(head[y],x);
    head[y] = 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 size[N];
int p,n;

void DFS(int x,int fa)
{
    for(int i=0;i<=p;++i)
        f[x][i] = inf;
    f[x][1] = 0;
    for(int i=head[x];i;i=edge[i].next)
        if(edge[i].to!=fa)
        {
            DFS(edge[i].to,x);
            for(int j=p;j>=1;--j)
            {
                int tmp = f[x][j]+1;
                for(int k=1;k<j;++k)
                    tmp = min(tmp,f[x][k]+f[edge[i].to][j-k]);
                f[x][j] = tmp;
            }
        }
}

bool in[N];

int main()
{
    n = read(), p = read();
    for(int i=1;i<n;++i)
    {
        int x = read(),y = read();
        in[y] = true;
        add(x,y);
    }
    int ans = 0x7fffff;
    for(int i=1;i<=n;++i)
        if(!in[i])
            DFS(i,i),ans=f[i][p];
    for(int i=1;i<=n;++i)
        ans = min(ans,f[i][p]+1);
    cout<<ans<<endl;
}

Title - Artist
0:00

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

TOP