2042.cpp

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

/*  This Code is Submitted by wywcgs for Problem 2042 on 2006-05-18 at 17:39:23 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int PN = 24, L = 24;
const int MN = 128;

class Person {
public:
	int fn;
	char name[L];
	bool rcv[MN];
	void clear(int n) { fn = n; memset(rcv, false, sizeof(rcv)); }
	int result(int o) { return rcv[o] ? fn : 0; }
};

class Msg {
public:
	int b, t1, t2;
	char status[3][L];
	void make();
	void sort(int) const;
};
void Msg::make() {
	scanf("%d %d", &t1, &t2);
	int i;
	for(i = 0; i < 3; i++) scanf("%s", status[i]);
}
void Msg::sort(int sn) const {
	if(sn < t1) printf("%s ", status[0]);
	else if(sn < t2) printf("%s ", status[1]);
	else printf("%s ", status[2]);
}

int main()
{
	int n, i, j, k;
	Person p[PN];
	Msg msg[MN];
	bool send[PN][PN];

	while(scanf("%d", &n) != EOF && n != 0) {
		memset(send, false, sizeof(send));
		for(i = 0; i < n; i++) {
			int m;
			for(j = 0; scanf("%d", &m) != EOF && m != 0; j++) send[i][m-1] = true;
			p[i].clear(j);
		}
		for(k = 0; k < n; k++)
			for(i = 0; i < n; i++)
				for(j = 0; j < n; j++) send[i][j] |= send[i][k] & send[k][j];
		int mn;
		for(mn = 0; scanf("%d", &msg[mn].b) != EOF && msg[mn].b != 0; mn++)
			msg[mn].make();
		for(i = 0; i < n; i++) scanf("%s", p[i].name);
		for(i = 0; i < mn; i++) {
			int stack[PN], top = 0;
			p[msg[i].b-1].rcv[i] = true; stack[top++] = msg[i].b-1;
			while(top > 0) {
				int x = stack[--top];
				for(j = 0; j < n; j++)
					if(send[x][j] && !p[j].rcv[i]) { p[j].rcv[i] = true; stack[top++] = j; }
			}
		}
		for(i = 0; i < n; i++) {
			printf("%s: ", p[i].name);
			for(j = 0; j < mn; j++) msg[j].sort(p[i].result(j));
			putchar('\n');
		}
	}
	
	return 0;
}