2040.cpp

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

/*  This Code is Submitted by wywcgs for Problem 2040 on 2006-02-11 at 03:33:43 */ 
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX = 1024;
const int INF = -1000000000;

class Sentence {
public:
	int o, tar;
	bool assign;
	vector<int> sub;
	void make();
};
void Sentence::make() {
	char state[8];
	scanf("%*s %d %*s %s", &tar, state); tar--;
	assign = (state[0] == 't');
}

Sentence s[MAX];
int truth, tn;
bool vst[MAX], a[MAX], state[MAX];

int assign(int, bool);
inline void push(int*, int&, int);

int main()
{
	int i, n;

	for(i = 0; i < MAX; i++) s[i].o = i;
	while(scanf("%d", &n) != EOF && n != 0) {
		truth = 0; memset(vst, false, sizeof(vst));
		for(i = 0; i < n; i++) s[i].sub.clear();
		for(i = 0; i < n; i++) {
			s[i].make();
			s[s[i].tar].sub.push_back(i);
		}
		for(i = 0; i < n; i++)
			if(truth >= 0 && !vst[i])
				truth += max(assign(i, true), assign(i, false));
		if(truth < 0) printf("Inconsistent\n");
		else printf("%d\n", truth);
	}
	
	return 0;
}

int assign(int b, bool ass)
{
	int stack[MAX], top = 0;
	vector<int>::iterator it;
	
	memset(a, false, sizeof(a)); tn = 0;
	state[b] = ass; push(stack, top, b);
	while(top > 0) {
		int p = stack[--top];
		if(a[s[p].tar] && (state[p] == s[p].assign) != state[s[p].tar]) return INF;
		state[s[p].tar] = (state[p] == s[p].assign); push(stack, top, s[p].tar);
		for(it = s[p].sub.begin(); it != s[p].sub.end(); it++) {
			if(a[*it] && (state[*it] == s[*it].assign) != state[p]) return INF;
			state[*it] = (s[*it].assign == state[p]); push(stack, top, *it);
		}
	}
	
	return tn;
}
inline void push(int* stack, int& top, int e)
{
	if(a[e]) return;
	stack[top++] = e; vst[e] = a[e] = true;
	if(state[e]) tn++;
}