2230.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 2230 on 2006-05-16 at 11:44:37 */ 
#include <cstdio>
#include <cstring>
#include <map>
#include <algorithm>
using namespace std;

const int PM = 1024;
const int L = 12;

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

class Person {
public:
	static int gd;
	char name[L];
	int g[PM], parent, d;
	void clear(char*);
	bool operator <(const Person&) const;
};
int Person::gd;
void Person::clear(char* nm) {
	strcpy(name, nm); memset(g, 0, sizeof(g)); g[0] = 1;
	parent = -1; d = 0;
}
bool Person::operator <(const Person& p) const {
	if(g[Person::gd] != p.g[Person::gd]) return g[Person::gd] > p.g[Person::gd];
	else return strcmp(name, p.name) < 0;
}

map<char*, int, cmp> dict;
Person p[PM];
int pn;

int order(char*);

int main()
{
	int n, t, T, i, j;

	scanf("%d", &T);
	for(t = 1; t <= T; t++) {
		if(t != 1) putchar('\n');
		scanf("%d %d", &n, &Person::gd);
		dict.clear(); pn = 0;
		for(i = 0; i < n; i++) {
			char pnt[L]; int m; scanf("%s %d", pnt, &m);
			int o = order(pnt); p[o].d = m;
			for(j = 0; j < m; j++) {
				char son[L]; scanf("%s", son);
				p[order(son)].parent = o;
			}
		}
		printf("Tree %d:\n", t);
		if(Person::gd >= pn) continue;
		int stack[PM], top = 0;
		for(i = 0; i < pn; i++)
			if(p[i].d == 0) stack[top++] = i;
		while(true) {
			int b = stack[--top], po = p[b].parent;
			if(po == -1) break;
			if(--p[po].d == 0) stack[top++] = po;
			for(i = 1; i <= Person::gd; i++) p[po].g[i] += p[b].g[i-1];
		}
		sort(p, p+pn);
		int pf = -1;
		for(i = 0; i < pn; i++) {
			int r = p[i].g[Person::gd];
			if(r == 0 || (i >= 3 && r != pf)) break;
			else printf("%s %d\n", p[i].name, r);
			pf = r;
		}
	}
	
	return 0;
}

int order(char* name)
{
	if(dict.count(name)) return dict.find(name)->second;
	int o = pn++; p[o].clear(name);
	dict[p[o].name] = o; return o;
}