POJ 3585 Accumulation Degree

二次扫描与换根法

用于解决无根树,对于每一个节点作为根时都要统计

做法:

1.先以任意一个节点为根,做树形DP,保存每个节点的DP值

2.然后自上而下dfs,对于每个节点考虑以他为根的最大值

#include <iostream>

#include <cstring>

#include <cstdio>

#include <algorithm>

using namespace std;

const int MAXN = 200505;

int init() {

	int rv = 0, fh = 1;

	char c = getchar();

	while(c < '0' || c > '9') {

		if(c == '-') fh = -1;

		c = getchar();

	}

	while(c >= '0' && c <= '9'){

		rv = (rv<<1) + (rv<<3) + c -'0';

		c = getchar();

	}

	return fh * rv;

}

int T, n, f[MAXN], c[MAXN], degree[MAXN], head[MAXN], nume, rot;

bool fff[MAXN];

struct edge{

	int to, nxt, flow;

}e[MAXN << 1];

void adde(int from, int to, int flow) {

	e[++nume].to = to;

	e[nume].flow = flow;

	e[nume].nxt = head[from];

	head[from] = nume;

}

void dfs1(int u) {

	fff[u] = 1;

	for(int i = head[u]; i ; i = e[i].nxt) {

		int v = e[i].to;

		if(fff[v]) continue;

		if(degree[v] == 1) {f[u] += e[i].flow;}

		else {dfs1(v); f[u] += min(f[v], e[i].flow);}

	}

}

void dfs2(int u) {

	fff[u] = 1;

	for(int i = head[u]; i; i = e[i].nxt) {

		int v = e[i].to;

		if(fff[v]) continue;

		c[v] = f[v];

		if(degree[u] == 1) c[v] += e[i].flow;

		else {

			c[v] += min(c[u] - min(f[u], e[i].flow), e[i].flow);

		}

		dfs2(v);

	}

}

int main() {

	T = init();

	while(T--) {

		n = init();

		memset(fff, 0, sizeof(fff));

		memset(f, 0, sizeof(f));

		memset(c, 0, sizeof(c));

		memset(degree, 0, sizeof(degree));

		memset(head, 0, sizeof(head));

		memset(e, 0, sizeof(e));

		nume = 0;

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

			int u = init(), v = init(), flow = init();

			adde(u, v, flow); adde(v, u, flow);

			degree[u]++; degree[v]++;

		}

		rot = 1;

		dfs1(rot);

		c[rot] = f[rot];

		memset(fff, 0, sizeof(fff));

		dfs2(rot);

		int ans = 0;

		for(int i = 1;i <= n; i++) ans = max(ans, c[i]);

		cout << ans << endl;

	}

	return 0;

}

巴特西

POJ 3585 Accumulation Degree

二次扫描与换根法

最新文章

热门文章