2503.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/* This Code is Submitted by wywcgs for Problem 2503 on 2007-06-05 at 18:31:33 */
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

const int N = 256;
const int INF = 1 << 28;

struct cmp {
	bool operator ()(const char* s1, const char* s2) const
		{ return strcmp(s1, s2) < 0; }
};

vector<int> g[N];
int n, m, nk, cc[N], cost[N][N], cnt[N];
map<const char*, int, cmp> dict;
char name[N][N];
bool root[N];

int getNum(char*);
void dfs(int);

int main()
{
	while(scanf("%d %d", &n, &m) == 2) {
		n++; dict.clear(); nk = 0;
		for(int i = 0; i < n; i++) g[i].clear();
		memset(root, true, sizeof(root));
		for(int i = 1; i < n; i++) {
			char nm[N]; int ct;
			scanf("%s %d", nm, &ct);
			int num = getNum(nm); cc[num] = ct;
			while(true) {
				char c;
				while((c = getchar()) == ' ');
				if(c == '\n') break;
				ungetc(c, stdin);
				scanf("%s", nm);
				int num1 = getNum(nm);
				g[num].push_back(num1); root[num1] = false;
			}
		}
		for(int i = 1; i < n; i++)
			if(root[i]) g[0].push_back(i);
		cc[0] = INF; dfs(0);
		int res = INF;
		for(int i = m; i <= n; i++) res <?= cost[0][i];
		printf("%d\n", res);
	}
	return 0;
}

int getNum(char* str)
{
	if(!dict.count(str)) {
		strcpy(name[nk], str);
		dict[name[nk]] = nk; nk++;
	}
	return dict[str]+1;
}
void dfs(int u)
{
	cost[u][0] = 0; cnt[u] = 1;
	int sum = 0;
	for(int i = 1; i < n; i++) cost[u][i] = INF;
	for(int i = 0; i < (int)g[u].size(); i++) {
		int v = g[u][i];
		dfs(v); cnt[u] += cnt[v];
		for(int j = sum; j >= 0; j--)
			for(int k = 0; k <= cnt[v]; k++)
				cost[u][j+k] <?= cost[u][j]+cost[v][k];
		sum += cnt[v];
	}
	cost[u][cnt[u]] = cc[u];
}