hdu2415(树上背包)

时间：2020-12-13 17:01:52

这道题好像没什么人写题解，于是写了一发

题意：有个坏蛋想要参加竞选，需要得到m个人的支持，买通第i个人(1<=i<=n)需要一个cost[i]，同时这些人又有上下属关系，只要买通了领导，他的下属（可以是下属的下属）也会给你投票，问最少要花多少钱

数据范围：N<=200,m<=n;

其实就是比较裸的树上分组背包，每个子节点的背包是一个组，选自己也是一个组，dfs搞一搞就好了，然而字符串处理实在恶心.....

#include<string>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<cstdio>

#include<cmath>

#include<vector>

#include<map>

#include<queue>

using namespace std;

const int MAX=<<;

int n,m;

map<string,int>dui;

vector<int>arr[];

char str[],tmp[];

int dp[][],fa[],siz[],cost[],cnt=;

void dfs1(int now)

{

    int i,j;

    siz[now]=;

    for(i=;i<arr[now].size();i++)

    {

        int v=arr[now][i];

        dfs1(v);

        siz[now]+=siz[v];

    }

}

void dfs(int now)

{

    int i,j,k;

    for(i=;i<arr[now].size();i++)

    {

        dfs(arr[now][i]);

        int v=arr[now][i];

        for(j=m;j>=;j--)for(k=;k<=j;k++)dp[now][j]=min(dp[now][j],dp[now][j-k]+dp[v][k]);

    }

    if(now!=n+)for(i=;i<=min(m,siz[now]);i++)dp[now][i]=min(cost[now],dp[now][i]);

    return ;

}

int main()

{

    int i,j;

    char ss[];

    while(scanf("%s",ss)!=EOF)

    {

        n=;

        cnt=;

        if(ss[]=='#')return ;

        for(i=;i<strlen(ss);i++)n*=,n+=ss[i]-'';

        scanf("%d",&m);

        int i,j;

        for(i=;i<=n+;i++)arr[i].clear();

        dui.clear();

        getchar();

        for(i=;i<=n+;i++)fa[i]=i;

        for(i=;i<n;i++)

        {

            gets(str);

            int len=strlen(str);

            for(j=;j<len;j++)if(str[j]==' ')break;

            int pos=j;

            memset(tmp,,sizeof(tmp));

            for(j=;j<pos;j++)tmp[j]=str[j];

            string a=tmp;

            if(!dui[a])dui[a]=++cnt;

            int name1=dui[a],costs=;

            while(str[pos]>''||str[pos]<'')pos++;

            for(j=pos;;j++)

            {

                if(str[j]=='\0'||str[j]>''||str[j]<'')

                {

                    pos=j;

                    break;

                }

                costs*=;

                costs+=str[j]-'';

            }

            cost[name1]=costs;

            int nums=;

            string b;

            for(j=pos+;j<len;j++)

            {

                if(str[j]!=' ')

                {

                    tmp[nums++]=str[j];

                    if(str[j+]==' '||str[j+]=='\0')

                    {

                        tmp[nums++]='\0';

                        b=tmp;

                        nums=;

                        if(!dui[b])dui[b]=++cnt;

                        int name2=dui[b];

                        arr[name1].push_back(name2);

                        fa[name2]=name1;

                    }

                }

            }

        }

        for(i=;i<=n+;i++)

        {

            dp[i][]=;

            for(j=;j<=m;j++)dp[i][j]=MAX;

        }

        for(i=;i<=n;i++)if(fa[i]==i)arr[n+].push_back(i);

        dfs1(n+);

        dfs(n+);

        printf("%d\n",dp[n+][m]);

    }

}

/*

9 5

A 45 B C

B 20

C 30

D 60 E F

E 20

F 50 G H

G 10

H 25 I

I 15

*/

相关文章