Bribing FIPA

原题：

PDF
QOJ

题意：

在 $ FIPA $ 即将有一场投票来决定下一届 $ IPWC $ 的举办地，而某个国家的代表想通过赠送钻石争取其他国家的投票。他已经知道了争取到每一个国家的选票各需要的钻石的数量，但是因为有一些贫弱的国家会与其直接或间接附属于的大国投相同国家的票，所以他不需要给每一个国家钻石以争取选票。

比如， $ C $ 国家附属于 $ B $ 国家，而 $ B $ 国家附属于 $ A $ 国家，则在向A国家赠送礼物后，可以获得$ABC$三国的选票。已知不存在一个国家附属于多个国家，且附属关系之间不存在环，试求在 $ N $ 个国家中获得至少 $ M $ 个国家的选票最少需要花费的钻石数量。

输入格式：

多组输入数据，每组的第一行为两个整数 $ N $ 、$M(1 /leq N /leq 200 , 0 /leq M /leq N)$，接下来的$N$行描述一个国家，每行依次为一个字符串表示国家的名称、一个数字描述需要的钻石数量、若干个字符串表示该国家直接的附属国。总输入以一行一个‘#’号表示结束。

输出格式：

对于每组输入数据，输出一行表示答案。

题意：

类似于间谍网络，有n个点，至少要得到m个点，购买一个点后，它的孩子都可以获得,购买一个点需要一个钻石，问最少需要多少钻石。

思路：

前言：

我第一眼看到这个题目，就想的是————这不就是间谍网络吗？？

但仔细看了一眼，题目要求要至少 $ M $ 个附属国，而 间谍网络是能够贿赂所有间谍。所以，是不一样的。

---

正文：

我们可以发现，一个大国的附属国，可以像树一样连一条边，这样的话 大国 就是 附属国 的 爸爸（题目中有说，不存在环）

这不就是我们可爱的树形dp吗？？？

按照套路设置dp状态：dp[u][i] : 以 u 为根，至少收买i个城市所需要的最小费用

按照套路来做状态转移方程 ： dp[u][i] = min(dp[u][i], dp[u][k] + dp[u][i – k]) (小小的解释一下哈： 其它不用多说，就是min里面后面那一个东东，是指它分成两个部分来求和)

另外需要注意的是：dp[u][i]求完后，需要比较一下直接买与
贿赂得到那一个更加划算。
即：dp[u][i] = min(dp[u][i], money[i])

最后答案自然就是:min(dp[u][m] ~ dp[u][n]) (至少m个国家支持)

注意：
初始值：
dp[u][0] = 0, dp[u][i] = 一个大数（注：不能大过ans的初始值，当初就是在这个地方卡了半天）

具体的细节看代码

树形dp代码：

void dfs(int u){
	dp[u][0] = 0;
	size[u] = 1;//赋初值
	for(int i = 0;i < G[u].size();i++){//遍历它的儿子
		int to = G[u][i];//它的儿子
		dfs(to);//从它儿子在做一次dfs
		size[u] += size[to];//求出以u为根的子树大小
		for(int j = n;j >= 0;j--)//收买国家的个数
			for(int k = j;k >= 0;k--)//类似于01背包，倒着循环
				dp[u][j] = min(dp[u][j], dp[u][j - k] + dp[to][k]);//状态转移方程，讲过，不过多赘述。
	}
	if(u != 0)//如果u不是超级原点，即根
		for(int i = 0;i <= size[u];i++)//遍历它的子树，直接买，还是通过贿赂获得
			dp[u][i] = min(dp[u][i], mon[u]);
}
//size[i]是指以i为根的子树大小

树形dp就是这么简单！但为什么这道题如此麻烦呢？？？
就是下面的重头戏了：

读入

不得不说，这题目思路是绿题，读入是紫题，读入真的是个毒瘤！！！

在讲到读入的时候，这边用到了两个 神奇的东西，科普一下（zyx讲给我的）：

1. fgets

fgets函数功能为从指定的流中读取数据，每次读取一行。其原型为：char *fgets(char *str, int n, FILE *stream);从指定的流 stream 读取一行，并把它存储在 str 所指向的字符串内。当读取 (n-1) 个字符时，或者读取到换行符时，或者到达文件末尾时，它会停止，具体视情况而定

(摘自《百度百科》)

主要功能:

从指定的流 stream 读取一行，并把它存储在str所指向的字符串内。当读取(n-1)个字符时，或者读取到换行符时，或者到达文件末尾时，它会停止，具体视情况而定。

但其实，这里的fgets主要是配合下面的这个函数（string，char都不行)

具体：百度百科

2 . sscanf（）

其中主要功能就是，在字符串中得到指定的数据；
举个栗子：

#include <stdio.h>
int main(void)
{
    char str[100] ="123568qwerSDDAE";
    char lowercase[100];
    int num;
    sscanf(str,"%d %[a-z]", &num, lowercase);
    printf("The number is: %d./n", num);
    printf("The lowercase is: %s.", lowercase);
    return 0;
}

输出为：

The number is: 123568.
The lowercase is: qwer.

具体：百度百科

（其实这两个都是C语言函数库里的）

---

这里的输入，主要是 大国 + 购买所需钻石 + 服从的若干个小国

国家名都是字符串。

这里可以选择两个方式来处理 ： Hash or map(正常人这里肯定选map啊！！)

这里我们选择用map来处理，同时记录每个点的入度，给每个国家编号

最后会得到若干个单独的树，但这样不好进行以后的操作，我们怎么操作呢？？

这是就可以用到————超级原点

我们可以将所有入度为0的点都与我们的“超级原点” 0 相连一条边

最后就可以得到一颗完整的树了，我们滴任务完成啦！！

具体看代码：

读入代码：

#include <bits/stdc++.h>
using namespace std;

------略-------

void clean_set(){
	memset(dp,0x3f,sizeof(dp));
	memset(rd,0,sizeof(rd));
	memset(size,0,sizeof(size));
	for(int i = 0;i <= n;i++) G[i].clear();
	mp.clear();
	cnt = 0;
}

int main(){
	char op[205];
	while(fgets(op,200,stdin)){
		if(op[0] == '#') break;
		sscanf(op,"%d%d",&n,&m);
		clean_set();
		string big,small;
		for(int i = 1;i <= n;i++){
			cin>>big;
			if(!mp[big]) mp[big] = ++cnt;
			scanf("%d",&mon[mp[big]]);
			while(getchar() != '/n'){
				cin>>small;
				if(!mp[small]) mp[small] = ++cnt;
				G[mp[big]].push_back(mp[small]);
				rd[mp[small]]++;
			}
		}
		for(int i = 1;i <= cnt;i++) if(rd[i] == 0) G[0].push_back(i);
		dfs(0);
		int ans = 0x3f3f3f3f;
		for(int i = m;i <= n;i++) ans = min(ans,dp[0][i]);
		printf("%d/n",ans);
	}
	
	return 0;
}

最后就不给全部代码了（几乎都放出来了，主要还是我懒）

希望大家能听懂！！！

谢谢！！！