2177.cpp

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

/*  This Code is Submitted by wywcgs for Problem 2177 on 2006-03-23 at 15:33:30 */ 
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

typedef unsigned int uint;
const int MAX = 1024;

int e, id[MAX], wage[MAX];
vector<int> nxt[MAX];

int cost(int);

class Task {
public:
	int o, base, pay;
	bool did[MAX];
	vector<int> wkr;
	void make(int);
	void act();
	void dep(Task&) const;
};
void Task::make(int co) {
	int dn, m, i; scanf("%d %d %d", &base, &dn, &m);
	o = co; wkr.clear(); nxt[o].clear();
	pay = -1; memset(did, false, sizeof(did));
	for(i = 0; i < dn+m; i++) {
		int a; scanf("%d", &a); a--;
		if(i < dn) { nxt[o].push_back(a); id[a]++; }
		else wkr.push_back(a);
	}
}
void Task::act() {
	uint i;
	for(i = 0; i < wkr.size(); i++)
		if(!did[wkr[i]]) { did[wkr[i]] = true; wage[wkr[i]] += cost(o); }
}
void Task::dep(Task& tn) const {
	int i;
	for(i = 0; i < e; i++) tn.did[i] = tn.did[i] || did[i];
}

Task task[MAX];

int main()
{
	int i, n;

	while(scanf("%d %d", &n, &e) != EOF && n != 0) {
		memset(wage, 0, sizeof(wage)); memset(id, 0, sizeof(id));
		for(i = 0; i < n; i++) task[i].make(i);
		int top = 0, stack[MAX];
		for(i = 0; i < n; i++) if(id[i] == 0) stack[top++] = i;
		while(top > 0) {
			int p = stack[--top]; task[p].act();
			for(i = 0; i < (int)nxt[p].size(); i++) {
				int o = nxt[p][i];
				task[p].dep(task[o]);
				if(--id[o] == 0) stack[top++] = o;
			}
		}
		printf("*****\n");
		for(i = 0; i < e; i++) printf("%d %d\n", i+1, wage[i]);
	}
	
	return 0;
}

int cost(int o)
{
	if(task[o].pay == -1) {
		uint i; task[o].pay = task[o].base;
		for(i = 0; i < nxt[o].size(); i++) task[o].pay += cost(nxt[o][i]);
	}
	return task[o].pay;
}