2185.cpp

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

/*  This Code is Submitted by wywcgs for Problem 2185 on 2006-03-27 at 15:37:00 */ 
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

const int MAX = 128;
const double NINF = -1e10;
const double eps = 1e-4;

int uo, id[MAX];
bool can, swing;
double lmt[MAX], um;

class Mobile {
public:
	int left, right;
	double len, w;
	char type;
	bool make();
};
bool Mobile::make() {
	int o; len = w = 0;
	if(scanf("%d", &o) == EOF || o <= 0) return false;
	scanf("\n%c\n", &type);
	if(type == 'B') {
		scanf("%lf %d %d", &len, &left, &right);
		id[left]++; id[right]++;
	} else {
		char ch = getchar();
		if(ch == 'X') { uo = o; w = NINF; }
		else { ungetc(ch, stdin); scanf("%lf", &w); }
	}
	return true;
}

Mobile mobile[MAX];

double balance(int, int, double);

int main()
{
	int i, n, top;

	while(true) {
		can = swing = true; memset(id, 0, sizeof(id));
		for(n = 0; mobile[n+1].make(); n++) ;
		if(n == 0) break;
		for(i = 0; i <= n; i++) lmt[i] = NINF;
		for(top = 1; id[top] != 0; top++) ;
		balance(0, top, 0);
		if(!can) printf("The mobile cannot be balanced.\n");
		else {
			printf("Object %d must have weight %.2lf\n", uo, um);
			printf("The mobile will%s swing freely.\n", swing ? "" : " not");
		}
	}
	
	return 0;
}

double balance(int f, int o, double mid)
{
	double l = mobile[o].len / 2;
	if(mid-l < lmt[f]) swing = false;
	lmt[f] = mid + l;
	if(mobile[o].type == 'D') return mobile[o].w;
	else {
		double left = balance(f+1, mobile[o].left, mid-l), right = balance(f+1, mobile[o].right, mid+l);
		if(right < 0) right = um = left;
		else if(left < 0) left = um = right;
		if(fabs(left-right) > eps) can = false;
		return left+right;
	}
}