首页 > 代码库 > POJ 1947 Rebuilding Roads

POJ 1947 Rebuilding Roads

树状DP第二题,这个题真的好复杂~~


题目大意:

有一个n个结点的树,问至少去掉几条边可以产生一个有p个节点的子树。


解题思路:

dp[i][j]表示以i号节点为根的子树,当有j个结点时最少需要去掉几条边。

初始化:当只有1个节点时,一定是连接它到孩子结点的所有边都去掉。

设某一孩子结点标号为v  则dp[i][j]=min(dp[i][j],dp[i][j-t]+dp[v][t]-1);

记录最小值是时,如果最小值在子树上需要加1,因为还有连接父亲结点的一条边没算。


下面是代码:

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <stdlib.h>
#include <vector>
#include <string>
#include <map>
#include <queue>
using namespace std;

int min(int a,int b)
{
    if(a>b)a=b;
    return a;
}
int max(int a,int b)
{
    if(a<b)a=b;
    return a;
}
struct node1
{
    int to,next;
} edge[155];
int head[155],num[155],sum[155],cnt,n,p,u,v,ans;
void addedge(int u,int v)
{
    edge[cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt++;
    num[u]++;
}
int dp[155][155];
void dfs(int src)
{
    dp[src][1]=num[src];
    sum[src]=1;
    if(head[src]!=-1)
    {
        int t=head[src];
        while(t!=-1)
        {
            dfs(edge[t].to);
            sum[src]+=sum[edge[t].to];
            for(int i=sum[src]; i>1; i--)
            {
                for(int j=1; j<i; j++)
                {
                    if(dp[src][i]==-1&&dp[src][i-j]!=-1&&dp[edge[t].to][j]!=-1)
                    {
                        dp[src][i]=dp[src][i-j]+dp[edge[t].to][j]-1;
                    }
                    else if(dp[src][i]!=-1&&dp[src][i-j]!=-1&&dp[edge[t].to][j]!=-1)
                    {
                        dp[src][i]=min(dp[src][i],dp[src][i-j]+dp[edge[t].to][j]-1);
                    }
                }
            }
            t=edge[t].next;
        }
    }
    if(dp[src][p]!=-1)
    {
        if(src=http://www.mamicode.com/=1)ans=min(ans,dp[src][p]);>