首页 > ACM题库 > HDU-杭电 > hdu 2415 Bribing FIPA-动态规划-[解题报告]C++
2014
01-26

hdu 2415 Bribing FIPA-动态规划-[解题报告]C++

Bribing FIPA

问题描述 :

There is going to be a voting at FIPA (Fédération Internationale de Programmation Association) to determine the host of the next IPWC (International Programming World Cup). Benjamin Bennett, the delegation of Diamondland to FIPA, is trying to seek other delegation’s support for a vote in favor of hosting IWPC in Diamondland. Ben is trying to buy the votes by diamond gifts. He has figured out the voting price of each and every country. However, he knows that there is no need to diamond-bribe every country, since there are small poor countries that take vote orders from their respected superpowers. So, if you bribe a country, you have gained the vote of any other country under its domination (both directly and via other countries domination). For example, if C is under domination of B, and B is under domination of A, one may get the vote of all three countries just by bribing A. Note that no country is under domination of more than one country, and the domination relationship makes no cycle. You are to help him, against a big diamond, by writing a program to find out the minimum number of diamonds needed such that at least m countries vote in favor of Diamondland. Since Diamondland is a candidate, it stands out of the voting process.

输入:

The input consists of multiple test cases. Each test case starts with a line containing two integers n (1 ≤ n ≤ 200) and m (0 ≤ m ≤ n) which are the number of countries participating in the voting process, and the number of votes Diamondland needs. The next n lines, each describing one country, are of the following form:

CountryName DiamondCount DCName1 DCName1

CountryName, the name of the country, is a string of at least one and at most 100 letters and DiamondCount is a positive integer which is the number of diamonds needed to get the vote of that country and all of the countries that their names come in the list DCName1 DCName1 … which means they are under direct domination of that country. Note that it is possible that some countries do not have any other country under domination. The end of the input is marked by a single line containing a single # character.

输出:

The input consists of multiple test cases. Each test case starts with a line containing two integers n (1 ≤ n ≤ 200) and m (0 ≤ m ≤ n) which are the number of countries participating in the voting process, and the number of votes Diamondland needs. The next n lines, each describing one country, are of the following form:

CountryName DiamondCount DCName1 DCName1

CountryName, the name of the country, is a string of at least one and at most 100 letters and DiamondCount is a positive integer which is the number of diamonds needed to get the vote of that country and all of the countries that their names come in the list DCName1 DCName1 … which means they are under direct domination of that country. Note that it is possible that some countries do not have any other country under domination. The end of the input is marked by a single line containing a single # character.

样例输入:

3 2
Aland 10
Boland 20 Aland
Coland 15
#

样例输出:

20

题意:给定N个国家,相互之间可能存在附属关系,现在想要贿赂m个国家,已知,贿赂一个国家,那么如果该国家拥有附属国,那么他的所有附属国都可以算作已经贿赂。

分析:按照国家之间的附属关系连边(有向),之后将森林转为一棵树,就变成了一棵树上的01背包了。

因为国家是用名字给出的,先用字典树给名字编号……

dp[i][j]表示第i个国家及其附属国中选j个国家的最小花费

之前一直过不了的题,现在居然1A了,主要是思路比较清晰

#include<iostream>
#include<algorithm>
#include<string.h>
#include<string>
#include<vector>
using namespace std;
const int N = 210;
int n,num,m,dp[N][N],w[N],in[N];
char s[20110];
bool vis[N];
vector<int> g[N];
typedef struct node    
{    
    int cnt;    
    struct node *next[52];   
}*tree,Trie;    
tree root;  
inline int GetNum(char *t){  
    tree p = root,newnode;  
    for(int i = 0;i < strlen(t); ++i){  
        int u = t[i] - 'a';  
        if(u<0) u=t[i]-'A'+26;
        if(p->next[u]==NULL)  
        {     
            newnode=(tree)malloc(sizeof(Trie));  
            newnode->cnt=-1;  
            for(int j=0;j<52;j++)  
                newnode->next[j]=NULL;  
            p->next[u]=newnode;  
            p=newnode;  
        }  
        else 
        p = p->next[u];  
    }  
    if(p->cnt == -1) //该节点未出现过  
        p->cnt = num ++;  
    return p->cnt;  
}  
void init()
{
    root=(tree)malloc(sizeof(Trie));  
    root->cnt=-1; 
    for(int j=0;j<52;j++)  
        root->next[j]=NULL; 
    num=1;
    memset(in,0,sizeof(in));
    for(int i=0;i<=n;i++)
        g[i].clear();
    for(int i=0;i<=n;i++)
        for(int j=0;j<=n;j++)
            dp[i][j]=INT_MAX;
}
int dfs(int u)
{
    int size=g[u].size();
    dp[u][0]=0;
    int t=0;
    for(int i=0;i<size;i++)
    {
        int v=g[u][i];
        int now=dfs(v);
        for(int j=t;j>=0;j--)//当前z树选择j个点
        {
            for(int k=0;k<=now;k++)//以v为根的子树选择k个点
                dp[u][j+k]=min(dp[u][j+k],dp[u][j]+dp[v][k]);
        }
        t+=now;
    }
    for(int i=1;i<=t+1;i++)//注意,这里就是题目的关键了,如果选择了父节点,那么父节点可以当成子树的所有状态值
        dp[u][i]=min(dp[u][i],w[u]);
    return t+1;
}
int main()
{
    char str[100],c[110];
    while(scanf("%s",str)==1)
    {
        if(strcmp(str,"#")==0)
            break;
        n=atoi(str);
        scanf("%d",&m);
        getchar();
        init();
        for(int i=0;i<n;i++)
        {
            gets(s);
            int len=strlen(s),cc=0,t=0,a,b;
            for(int j=0;j<=len;j++)
            {
                if(s[j]!=' ' && s[j]!='\0')
                  c[t++]=s[j];
                if(s[j]==' '||s[j]=='\0')
                {
                    cc++;
                    c[t]='\0';
                    t=0;
                    if(cc==1)
                        a=GetNum(c);
                    else if(cc==2)
                        w[a]=atoi(c);
                    else {
                        b=GetNum(c);
                        g[a].push_back(b);
                        in[b]++;
                    }
                }
            }
        }
        for(int i=1;i<=n;i++)//将森林转为树
        {
            if(in[i]==0)
                g[0].push_back(i);
        }
        w[0]=INT_MAX;//0节点是自己添加的,它对应的花费应该设定为正无穷,这样就不会选择这个点了
        dfs(0);
        printf("%d\n",dp[0][m]);
    }
    return 0;
}

 

解题转自:http://www.cnblogs.com/nanke/archive/2012/03/07/2384269.html


  1. 为什么for循环找到的i一定是素数叻,而且约数定理说的是n=p1^a1*p2^a2*p3^a3*…*pk^ak,而你每次取余都用的是原来的m,也就是n

  2. I like your publish. It is great to see you verbalize from the coronary heart and clarity on this essential subject matter can be easily noticed.

  3. a是根先忽略掉,递归子树。剩下前缀bejkcfghid和后缀jkebfghicd,分拆的原则的是每个子树前缀和后缀的节点个数是一样的,根节点出现在前缀的第一个,后缀的最后一个。根节点b出现后缀的第四个位置,则第一部分为四个节点,前缀bejk,后缀jkeb,剩下的c出现在后缀的倒数第2个,就划分为cfghi和 fghic,第3部分就为c、c