2168.cpp

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

/*  This Code is Submitted by wywcgs for Problem 2168 on 2006-03-13 at 12:19:41 */ 
#include <cstdio>
#include <cstring>
#include <cctype>
#include <map>
#include <algorithm>
using namespace std;

const int L = 10;
const int N_MAX = 128;
const int R_MAX = 2400;
const char R_SET[][4] = { "<", "<=", ">", ">=", "=" };
const int INF = 1 << 20;

struct cmp {
	bool operator ()(const char* s1, const char* s2) const {
		return strcmp(s1, s2) < 0;
	}
};

class Employe {
public:
	char name[L];
	int d[2];
	bool final;
	void make(char*);
	void show() const;
	bool operator <(const Employe&) const;
};
void Employe::make(char* str) {
	strcpy(name, str);
	final = isdigit(str[0]);
	d[0] = d[1] = (final ? 0 : INF);
}
void Employe::show() const {
	if(!isdigit(name[0])) printf("%s %d %d\n", name, -d[0], d[1]);
}
bool Employe::operator <(const Employe& e) const {
	return strcmp(name, e.name) < 0;
}

class Relation {
public:
	int b, e, len;
	void set(int, int, int, char*);
};
void Relation::set(int cb, int ce, int l, char* r) {
	b = cb; e = ce; len = -l;
	if(r[0] == '<') { swap(b, e); len = -len; }
	if(r[1] != '=') len--;
}

class Company {
private:
	int en, rn;
	bool ok;
	Employe e[N_MAX];
	Relation r[R_MAX];
	map<const char*, int, cmp> per;
	int ro(char* str) const { int i; for(i = 0; strcmp(R_SET[i], str); i++); return i; }
	int order(char*);
	void insert(int, int, int, char*);
public:
	bool make();
	void show();
};
int Company::order(char* str) {
	if(isdigit(str[0])) return 0;
	else if(per.count(str) != 0) return per.find(str)->second;
	else {
		e[en].make(str);
		insert(en, 0, 1, ">="); insert(0, en, -99999, ">=");
		per[e[en].name] = en; en++;
		return en-1;
	}
}
void Company::insert(int a, int b, int v, char* re) {
	if(re[0] == '=') { r[rn++].set(a, b, v, ">="); r[rn++].set(b, a, -v, ">="); }
	else r[rn++].set(a, b, v, re);
}
bool Company::make() {
	per.clear();
	en = 1; rn = 0; ok = true; e[0].make("0");
	char nm[2][L], op[L];
	while(true) {
		char *n1 = nm[0], *n2 = nm[1];
		if(scanf("%s", n1) == EOF) return false;
		else if(!strcmp(n1, "-")) return true;
		scanf("%s %s", op, n2);
		int a = -1, b = -1;
		if(isdigit(n1[0])) sscanf(n1, "%d", &a);
		if(isdigit(n2[0])) sscanf(n2, "%d", &b);
		if(a != -1 && b != -1) {
			switch(ro(op)) {
			case 0: if(a >= b) ok = false; break;
			case 1: if(a > b) ok = false; break;
			case 2: if(a <= b) ok = false; break;
			case 3: if(a < b) ok = false; break;
			case 4: if(a != b) ok = false; break;
			}
		} else {
			int len = max(max(a, b), 0);
			if(a != -1) {
				swap(n1, n2);
				if(op[0] != '=') op[0] = '<'+'>'-op[0];
			}
			insert(order(n1), order(n2), len, op);
		}
	}
}
void Company::show() {
	bool ex = true; int i, j;
	for(i = 0; i <= en && ex && ok; i++) {
		ex = false;
		for(j = 0; j < rn && ok; j++) {
			int bi = r[j].b, en = r[j].e, l = r[j].len;
			if(e[bi].d[1]+l < e[en].d[1])
				{ ex = true; e[en].d[1] = e[bi].d[1] + l; }
			if(e[en].d[0]+l < e[bi].d[0])
				{ ex = true; e[bi].d[0] = e[en].d[0] + l; }
		}
		if((ex && i == en) || (e[0].d[0] != 0 || e[0].d[1] != 0)) ok = false;
	}
	printf("%s\n", ok ? "OK" : "No solution");
	if(ok) {
		sort(e, e+en);
		for(i = 0; i < en; i++) e[i].show();
	}
}

int main()
{
	int t;
	Company c;
	
	for(t = 0; true; t++) {
		if(!c.make()) return 0;
		if(t != 0) putchar('\n');
		c.show();
	}
	
	return 0;
}