1077.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1077 on 2006-02-09 at 21:24:52 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX = 32;

class Node {
public:
	char kind;
	int delay, total;
	void make();
};
void Node::make() {
	scanf("\n%c %d", &kind, &delay);
	total = 0;
}

Node node[MAX];
bool input[MAX][MAX];
int n, in[MAX];

bool willTerminate();
void run();

int main()
{
	int clock, m, t, T, i;

	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		scanf("%d %d", &clock, &n);
		for(i = 0; i < n; i++) node[i].make();
		memset(input, false, sizeof(input)); memset(in, 0, sizeof(in));
		scanf("%d", &m);
		for(i = 0; i < m; i++) {
			int a, b;
			scanf("%d %d", &a, &b);
			if(!input[a][b]) input[a][b] = true, in[b]++;
		}
		if(!willTerminate()) printf("Circuit contains cycle.\n");
		else {
			int delay = 0;
			for(i = 0; i < n; i++) delay = max(delay, node[i].total);
			if(delay > clock) printf("Clock period exceeded.\n");
			else printf("Synchronous design. Maximum delay: %d.\n", delay);
		}
	}

	return 0;
}

bool willTerminate()
{
	bool remove[MAX] = { false };
	int i, stack[MAX], top = 0;

	for(i = 0; i < n; i++)
		if(node[i].kind == 's') stack[top++] = i, remove[i] = true;
	while(top > 0) {
		int p = stack[--top];
		for(i = 0; i < n; i++)
			if(!remove[i] && input[p][i] && --in[i] == 0)
				stack[top++] = i, remove[i] = true;
	}
	for(i = 0; i < n; i++)
		if(in[i] == 0 && !remove[i]) stack[top++] = i, remove[i] = true;
	while(top > 0) {
		int p = stack[--top];
		for(i = 0; i < n; i++)
			if(input[p][i]) {
				node[i].total = max(node[i].total, node[p].delay+node[p].total);
				if(!remove[i] && --in[i] == 0) stack[top++] = i, remove[i] = true;
			}
	}
	for(i = 0; i < n; i++)
		if(!remove[i]) return false;
	return true;
}