[ZJOI2012]旅游

看懂题意就好了。

就是相邻的城市连边，然后求图的直径。

/**
 * Problem:Journey
 * Author:Shun Yao
 * Time:2013.6.3
 * Result:Accepted
 */

#include <cstring>
#include <cstdio>
#include <algorithm>

const long Maxn = 200005;

long abs(long x) {
	return x < 0 ? -x : x;
}
long max(long x, long y) {
	return x > y ? x : y;
}
long min(long x, long y) {
	return x < y ? x : y;
}

class line {
public:
	long u, v, i;
	line() {}
	~line() {}
	line(long U, long V, long I):u(min(U, V)), v(max(U, V)), i(I) {}
} l[Maxn << 1];

bool cmpl(line a, line b) {
	return a.u != b.u ? a.u < b.u : a.v < b.v;
}

class gnode {
public:
	long v;
	gnode *next;
	gnode() {}
	~gnode() {}
	gnode(long V, gnode *ne):v(V), next(ne) {}
} *g[Maxn];

void add(long x, long y) {
	g[x] = new gnode(y, g[x]);
	g[y] = new gnode(x, g[y]);
}

long n, tot;
long q[Maxn], *L, *R;
long f[Maxn], d[Maxn][2];
long ans;
int main() {
	static long i, a, b, c;
	static gnode *e;
	freopen("journey.in", "r", stdin);
	freopen("journey.out", "w", stdout);
	scanf("%ld", &n);
	tot = 0;
	for (i = 1; i <= n - 2; ++i) {
		scanf("%ld%ld%ld", &a, &b, &c);
		if (abs(a % n - b % n) > 1 && abs(a - b) > 1)
			l[++tot] = line(a, b, i);
		if (abs(a % n - c % n) > 1 && abs(a - c) > 1)
			l[++tot] = line(a, c, i);
		if (abs(b % n - c % n) > 1 && abs(b - c) > 1)
			l[++tot] = line(b, c, i);
	}
	std::sort(l + 1, l + tot + 1, cmpl);
	for (i = 1; i <= tot; i += 2)
		add(l[i].i, l[i + 1].i);
	memset(f, 0, sizeof f);
	R = (L = &(*q = 1)) + 1;
	f[1] = -1;
	while (L != R) {
		for (e = g[*L]; e; e = e->next)
			if (!f[e->v])
				f[*(R++) = e->v] = *L;
		++L;
	}
	ans = 0;
	do {
		--L;
		d[*L][0] = 0;
		d[*L][1] = 0;
		for (e = g[*L]; e; e = e->next)
			if (f[e->v] == *L) {
				if (d[*L][0] < d[e->v][0] + 1) {
					d[*L][1] = d[*L][0];
					d[*L][0] = d[e->v][0] + 1;
				} else if (d[*L][1] < d[e->v][0] + 1)
					d[*L][1] = d[e->v][0] + 1;
			}
		ans = max(ans, d[*L][0] + d[*L][1] + 1);
	} while (L != q);
	printf("%ld", ans);
	fclose(stdin);
	fclose(stdout);
	return 0;
}