[조이2008] 기사.

3208 단어 2008
문제를 볼 때 하나의 독립집 문제처럼 데이터를 보고...
주로 모든 기사가 가지고 있고 유일하게 자신이 가장 싫어하는 기사가 있다.
그래서 전체 그림은 여러 개의 연결 블록이고 모든 연결 블록은 하나의 고리와 나무이다.
먼저 나무에 dp를 만들고,
두 개의 고리를 매거하여 각각 찾지 않을 수 있다.
링 dp도 쓸 수 있어요.
(나는 링 dp라고 썼다)
/**

 * Problem:[ZJOI2008]p5

 * Author:Shun Yao

 * Time:2013.5.30

 * Result:Accepted

 * Memo:DP

 */



#include <cstring>

#include <cstdio>



const long Maxn = 1000005;



long long max(long long x, long long y) {

	return x > y ? x : y;

}



void swap(long &x, long &y) {

	x ^= y;

	y ^= x;

	x ^= y;

}



long n, A[Maxn], fa[Maxn], ff[Maxn];

long long ans, f[Maxn][2];



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]);

}



void DP_Tree(long x) {

	static long q[Maxn], *l, *r;

	static gnode *e;

	r = (l = &(*q = x)) + 1;

	while (l != r) {

		for (e = g[*l]; e; e = e->next)	if (!ff[e->v]) {

			ff[e->v] = *l;

			*(r++) = e->v;

		}

		++l;

	}

	do {

		--l;

		f[*l][0] = 0;

		f[*l][1] = A[*l];

		for (e = g[*l]; e; e = e->next) if (ff[e->v] == *l) {

			f[*l][0] += f[e->v][1];

			f[*l][1] += f[e->v][0];

		}

		f[*l][1] = max(f[*l][1], f[*l][0]);

	} while (l != q);

}



long q[Maxn], *l, *r;

long st[Maxn << 1], stl;

long ST[Maxn], STl;

long d[Maxn];

long long h[Maxn];

void DP(long x) {

	static gnode *e;

	static long a, b;

	r = (l = &(*q = x)) + 1;

	fa[x] = -1;

	stl = 0;

	STl = 0;

	while (l != r) {

		for (e = g[*l]; e; e = e->next) if (e->v != fa[*l]) {

			if (!fa[e->v]) {

				d[e->v] = d[*l] + 1;

				fa[e->v] = *l;

				*(r++) = e->v;

			} else if (!stl) {

				a = *l;

				b = e->v;

				if (d[a] < d[b])

					swap(a, b);

				while (d[a] > d[b]) {

					st[++stl] = a;

					a = fa[a];

				}

				while (a != b) {

					st[++stl] = a;

					ST[++STl] = b;

					a = fa[a];

					b = fa[b];

				}

				st[++stl] = a;

				while (STl)

					st[++stl] = ST[STl--];

			}

		}

		++l;

	}

	static long i;

	for (i = 1; i <= stl; ++i)

		ff[st[i]] = -1;

	for (i = 1; i <= stl; ++i)

		DP_Tree(st[i]);

	static long long ret;

	h[0] = 0;

	h[1] = f[st[1]][1];

	for (i = 2; i < stl; ++i)

		h[i] = max(h[i - 2] + f[st[i - 1]][0] + f[st[i]][1], h[i - 1] + f[st[i]][0]);

	ret = h[stl - 1] + f[st[stl]][0];

	h[1] = 0;

	h[2] = f[st[2]][1];

	for (i = 3; i <= stl; ++i)

		h[i] = max(h[i - 2] + f[st[i - 1]][0] + f[st[i]][1], h[i - 1] + f[st[i]][0]);

	ans += max(h[stl] + f[st[1]][0], ret);

}



int main() {

	static long i, B;

	freopen("p5.in", "r", stdin);

	freopen("p5.out", "w", stdout);

	scanf("%ld", &n);

	for (i = 1; i <= n; ++i)

		g[i] = 0;

	for (i = 1; i <= n; ++i) {

		scanf("%ld%ld", A + i, &B);

		add(i, B);

	}

	memset(d, 0, sizeof d);

	memset(fa, 0, sizeof fa);

	memset(ff, 0, sizeof ff);

	ans = 0;

	for (i = 1; i <= n; ++i)

		if (!fa[i])

			DP(i);

	printf("%lld", ans);

	fclose(stdin);

	fclose(stdout);

	return 0;

}


좋은 웹페이지 즐겨찾기