Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

There is going to be a voting at FIPA (Federation 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 IPWC 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.

Input 

The input consists of multiple test cases. Each test case starts with a line containing two integers n (1n200) and m (0mn) 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 DCName₁ DCName₂...

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 DCName₁ DCName₂... 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

---

題目描述：

要用鑽石進行賄賂，以方便在下次選舉當選。

每個國家有支配關係，以及賄賂的成本。倘若打算賄賂該國家，則可以得到該所有支配關係中所有國家的投票(支配的支配，支配的支配的支配 ...)。

而當選至少要 m 票(含)，問最少賄賂成本為何？

題目解法：

支配關係肯定是一個樹形，而輸入肯定是多棵樹，你也可以多一個點讓它變一棵樹。

而考慮 dp[node][w] 表示子樹 node 的背包重量 w 的最少成本(w 為可得票數)。

則可以從支配關係的子節點中得到票數 i 個的最少成本，從其進行dp背包。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <map>
#include <vector>
#define oo 0x3f3f3f3f
using namespace std;
int n, m;
vector<int> g[205];
int price[205];
int dfs(int nd, int dp[]) {
	int son = 1;//itself
	int buf[205];
	int i, j, k;
	for(i = 1; i <= n; i++)
		dp[i] = oo;
	dp[0] = 0;
	for(vector<int>::iterator it = g[nd].begin();
		it != g[nd].end(); it++) {
		int tmp = dfs(*it, buf);
		son += tmp;
		for(j = son; j >= 0; j--)
			for(i = 0; i <= tmp; i++)
				if(j-i >= 0)
					dp[j] = min(dp[j], dp[j-i]+buf[i]);
	}
	dp[son] = min(dp[son], price[nd]);
	return son;
}
int main() {
	char s[1005];
	string country;
	int i, j, k, p, q, r;
	while(scanf("%d %d", &n, &m) == 2) {
		map<string, int> R;
		while(getchar() != '\n');
		for(i = 0; i < 205; i++)
			g[i].clear();
		int size = 0;
		int indeg[205] = {};
		for(i = 0; i < n; i++) {
			gets(s);
			stringstream sin(s);
			sin >> country >> p;
			int &x = R[country];
			if(x == 0)	x = ++size;
			price[x] = p;
			while(sin >> country) {
				int &y = R[country];
				if(y == 0)	y = ++size;
				g[x].push_back(y);
				indeg[y]++;
			}
		}
		int dp[205], buf[205];
		for(i = 1; i <= n; i++)
			dp[i] = oo;
		dp[0] = 0;
		for(k = 1; k <= n; k++) {
			if(indeg[k] == 0) {
				dfs(k, buf);
				for(j = n; j >= 0; j--)
					for(i = 0; i <= n; i++)
						if(j-i >= 0)
							dp[j] = min(dp[j], dp[j-i]+buf[i]);
			}
		}
		int mn = oo;
		for(i = m; i <= n; i++)
			mn = min(mn, dp[i]);
		printf("%d\n", mn);
	}
	return 0;
}