Bribing FIPA
Time Limit:2000MS |
|
Memory Limit:65536K |
Total Submissions:3380 |
|
Accepted:1058 |
Description
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 leastmcountries vote in favor of Diamondland. Since Diamondland is a candidate, it stands out of the voting process.
Input
The input consists of multiple test cases. Each test case starts with a line containing two integersn(1 ≤n≤ 200) andm(0 ≤m≤n) which are the number of countries participating in the voting process, and
the number of votes Diamondland needs. The nextnlines, each describing one country, are of the following form:
CountryNameDiamondCountDCName1DCName1...
CountryName, the name of the country, is a string of at least one and at most 100 letters andDiamondCountis 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 listDCName1DCName1... 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.
Output
For each test case, write a single line containing a number showing the minimum number of diamonds needed to gain the vote of at least m countries.
Sample Input
3 2
Aland 10
Boland 20 Aland
Coland 15
#
Sample Output
20
Source
|
题意:
一人去竞选。共有n(1<=n<=200)个国家参与投票。通过贿赂可以得到他们的选票。而贿赂不同的国家所花费的代价也不同。国家之间有大哥和小弟的关系。如果贿赂了它的大哥就不用贿赂小弟了。因为小弟会跟着大哥投票。先问你
得到m个国家选票所花费的最小代价。
思路:
这题树形DP的模型还是很简单的。比较难弄的是输入。因为它没告诉你它后面有多少小弟。而且读n,m也必须用字符
数组读。因为它是用'#'来结束输入的。。--||。虽然花了不少功夫。但是也学了不少东西。还是值得的。
处理好输入后面就很简单了。可以用国家的名字和标号建立一个映射。然后用标号建单向边就行了。这次换了下风格。用vector存的边。树建好后就可以DP了。要注意的是题目给的是森林。所以增加0号节点把它变为有根树。
dp[i][j]表示。节点i获得j票的最小代价。
dp[i][j]=min(dp[i][j],dp[i][k]+dp[son][j-k])。son为i的儿子结点。
还有很多细节。
详细见代码:
#include <iostream>
#include<algorithm>
#include<sstream>//for stringstream
#include<string.h>
#include<stdio.h>
#include<math.h>
#include<vector>
#include<string>
#include<queue>
#include<map>
using namespace std;
const int maxn=250;
const int INF=0x3f3f3f3f;
int n,m;
int cost[maxn];
int dp[maxn][maxn];
char buff[250110];
vector<int> edge[maxn];
map<string,int> mp;
string name;
bool nroot[maxn];// if the node is root nroot=0;
int dfs(int u)
{
int i,j,k,v,sz,lim,t,tot=1;
sz=edge[u].size();
dp[u][0]=0;
for(i=0;i<sz;i++)
{
v=edge[u][i];
t=dfs(v);
tot+=t;
for(j=tot;j>0;j--)
{
lim=min(j,t);
for(k=1;k<=lim;k++)
dp[u][j]=min(dp[u][j],dp[u][j-k]+dp[v][k]);
}
}
for(i=1;i<=tot;i++)//it's very important!
dp[u][i]=min(dp[u][i],cost[u]);
return tot;//the size of subtree.
}
int main()
{
int i,cnt,u,v;
stringstream s;//attention!
while(gets(buff))// gets() if empty return NULL.
{
if(buff[0]=='#')//a big track.
break;
sscanf(buff,"%d%d",&n,&m);
cnt=1;// 0 is the root
cost[0]=INF;
mp.clear();
memset(nroot,0,sizeof nroot);
memset(dp,0x3f,sizeof dp);
for(i=0;i<=n;i++)
edge[i].clear();
for(i=0;i<n;i++)
{
gets(buff);
s.clear();
s.str(buff);//a very useful method.
s>>name;
if(!mp[name])//build a reflect.
mp[name]=cnt++;
u=mp[name];
s>>cost[u];
while(s>>name)
{
if(!mp[name])
mp[name]=cnt++;
v=mp[name];
nroot[v]=true;
edge[u].push_back(v);//build edges.
}
}
for(i=1;i<cnt;i++)
if(!nroot[i])//if the node is root.
edge[0].push_back(i);
dfs(0);
printf("%d\n",dp[0][m]);
}
return 0;
}
分享到:
相关推荐
关于poj dp分类,我一直寻找dp的分类,终于找到了,也上传一下
Poj 3342 这是一道树状dp题目,题意是这样的,一个公司,每个人有且仅有一个Boss,除了最大的Boss没有Boss(显然),现在要参加一个聚会,要求参加的人数最多,但是棘手的.......
poj2342,树形dp,dp[i][0]表示i不参加party,其下属(包括非直接下属)能得到的最优值。dp[i][1]表示i参加的其下属和他能得到的最优值。
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
这是一道很不错的题目,dp解决的经典例子,是学习dp,和练习的好题目。。。。
北大POJ1015-Jury Compromise【动态规划DP】 解题报告+AC代码
NULL 博文链接:https://200830740306.iteye.com/blog/603493
这是黑不来就的poj上的所有dp题目的大型分类 好使好用
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
1.把自己的污水排到河里V 2.把自己的污水送到右边> 3.把自己的污水送到左边
poj 2763 程序 线段树 LCA 2000MS AC
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
2遍dp poj_3613解题报告 poj_3613解题报告
poj分类poj分类poj分类poj分类
北大POJ1159-Palindrome 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
NULL 博文链接:https://128kj.iteye.com/blog/1705139
POJ题解 个人写法 线段树每个人都不一样
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告