2512.cpp

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

/* This Code is Submitted by wywcgs for Problem 2512 on 2007-06-24 at 18:54:26 */
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cctype>
using namespace std;
 
const int N = 256;
typedef vector<int> VI;
 
#define CLEAR(a, b) memset(a, b, sizeof(a))
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define PB push_back
#define FOREACH(i, v) for(VI::iterator i = (v).begin(); i != (v).end(); i++)
#define ALL(a) (a).begin(), (a).end()
 
bool pre[N][N], conf[N][N];
int wei[N], n;
 
int calcWei(int);
bool cmp(int a, int b) { return wei[a] > wei[b]; }
 
int main()
{
	while(true) {
		CLEAR(pre, false); CLEAR(conf, false);
		int v, m; n = 0;
		for(m = 0; scanf("%d", &v) != EOF && v != 0; m++) {
			char str[10]; v--;
			n >?= v+1;
			while(scanf("%s", str) != EOF && str[0] != '0') {
				int l = strlen(str), type = 0;
				if(isdigit(str[l-1])) type = 1;
				int u; sscanf(str, "%d", &u); u--; n >?= u+1;
				if(type == 1) conf[u][v] = conf[v][u] = true;
				else if(str[l-1] == 'd') pre[v][u] = true;
				else pre[u][v] = true;
			}
		}
		if(m == 0) break;
		CLEAR(wei, -1);
		FOR(i, 0, n)
			if(wei[i] == -1) calcWei(i);
		int d[N] = { 0 };
		FOR(i, 0, n) FOR(j, 0, n)
			if(pre[i][j]) d[j]++;
		VI Q;
		FOR(i, 0, n) if(d[i] == 0) Q.PB(i);
		int day = 0, choose[N];
		CLEAR(choose, -1);
		for(; !Q.empty(); day++) {
			VI Qs; Qs.clear();
			sort(ALL(Q), cmp);
			FOREACH(i, Q) {
				int u = *i;
				bool can = true;
				FOR(j, 0, n) if(choose[j] == day && conf[j][u])
					{ can = false; break; }
				if(!can) { Qs.PB(u); continue; }
				choose[u] = day;
				FOR(j, 0, n) if(pre[u][j]) {
					d[j]--;
					if(d[j] == 0) Qs.PB(j);
				}
			}
			Q = Qs;
		}
		printf("%d\n", day);
	}
	return 0;
}
 
int calcWei(int u)
{
	wei[u] = 1;
	FOR(i, 0, n) if(pre[u][i]) wei[u] += calcWei(i);
	return wei[u];
}