2096.cpp

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

/*  This Code is Submitted by wywcgs for Problem 2096 on 2005-12-18 at 23:19:12 */ 
#include <cstdio>
#include <cstring>
#include <list>
#include <algorithm>
using namespace std;

typedef pair<int, int> pii;

const int MAX = 10240;

class Village {
public:
	list<pii> nei;
	int d, o;
	void clear();
	void link(Village&, int);
};
void Village::clear() {
	d = 0;
	nei.clear();
}
void Village::link(Village& v, int l)
{
	nei.push_back(pii(v.o, l));
	v.nei.push_back(pii(o, l));
	d++; v.d++;
}

int main()
{
	Village v[MAX];
	int d[MAX], n, i;
	bool visit[MAX];
	char line[64];
	
	for(i = 0; i < MAX; i++) {
		v[i].o = i;
	}
	while(gets(line) != NULL) {
		memset(visit, false, sizeof(visit));
		n = 0;
		while(strcmp(line, "*")) {
			int a, b, l;
			if(sscanf(line, "%d %d %d", &a, &b, &l) == 3) {
				a--; b--;
				for(i = 0; i < 2; i++) {
					int o = (i == 0 ? a : b);
					if(!visit[o]) {
						visit[o] = true;
						v[o].clear();
						n++;
					}
				}
				v[a].link(v[b], l);
			}
			gets(line);
		}
		memset(d, 0, sizeof(d));
		int stack[MAX], top = 0, longest = 0;
		for(i = 0; i < n; i++) {
			if(v[i].d == 1) {
				stack[top++] = i;
			}
		}
		while(top > 0) {
			int t = stack[--top];
			list<pii>::iterator it;
			for(it = v[t].nei.begin(); it != v[t].nei.end(); it++) {
				int o = it->first, len = it->second;
				if(d[o] != -1) {
					longest = max(longest, d[o]+d[t]+len);
					d[o] = max(d[o], d[t]+len);
					if(--v[o].d == 1) {
						stack[top++] = o;
					}
				}
			}
			d[t] = -1;
		}
		printf("%d\n", longest);
	}

	return 0;
}