首页 > 代码库 > 【CodeVS 1218】【NOIP 2012】疫情控制

【CodeVS 1218】【NOIP 2012】疫情控制

http://codevs.cn/problem/1218/

比较显然的倍增,但是对于跨过根需要很多讨论,总体思路是贪心。

技术分享写了一上午,不想再说什么了

#include<cstdio>#include<cstring>#include<algorithm>using namespace std;typedef long long ll;const int N = 100003;int in() {	int k = 0, fh = 1; char c = getchar();	for(; c < ‘0‘ || c > ‘9‘; c = getchar())		if (c == ‘-‘) fh = -1;	for(; c >= ‘0‘ && c <= ‘9‘; c = getchar())		k = (k << 3) + (k << 1) + c - ‘0‘;	return k * fh;}struct node {int nxt, to, w;} E[N << 1];struct data {	ll left; int from;	bool operator < (const data &A) const {		return left < A.left;	}} A[N], B[N];struct data2 {	int id, dis;	bool operator < (const data2 &A) const {		return dis < A.dis;	}} P[N];int f[N][18], n, m, cnt = 0, point[N], L[N], R[N], w[N], Army[N], a[N], nxt[N], upto[N];ll c[N][18];bool mark[N];void ins(int u, int v, int w) {E[++cnt] = (node) {point[u], v, w}; point[u] = cnt;}void dfs(int x) {	L[x] = ++cnt;	w[cnt] = x;	for(int i = point[x]; i; i = E[i].nxt)			if (E[i].to != f[x][0]) {			f[E[i].to][0] = x;			c[E[i].to][0] = E[i].w;			dfs(E[i].to);		}	R[x] = cnt;}void pushup_mark(int x) {	if (mark[x]) return;	bool flag = false, marknow = true;	for(int i = point[x]; i; i = E[i].nxt)		if (E[i].to != f[x][0]) {			pushup_mark(E[i].to);			flag = true;			marknow &= mark[E[i].to];		}	if (flag) mark[x] = marknow;}bool can(ll up) {	int tmp, tot = 0, tot2 = 0, tot3 = 0; ll ret;	memset(mark, 0, sizeof(bool) * (n + 1));	for(int i = 1; i <= m; ++i) {		ret = up; tmp = Army[i];		for(int j = 17; j >= 0; --j)			if (f[tmp][j] && f[tmp][j] != 1 && c[tmp][j] <= ret) {				ret -= c[tmp][j];				tmp = f[tmp][j];			}		if (c[tmp][0] <= ret) A[++tot] = (data) {ret - c[tmp][0], tmp};		else mark[tmp] = true;	}			for(int i = point[1]; i; i = E[i].nxt)		pushup_mark(E[i].to);		for(int i = 1; i <= tot; ++i)		if (!mark[A[i].from])			if (A[i].left <= c[A[i].from][0])				mark[A[i].from] = true;			else				B[++tot3] = A[i];		else			B[++tot3] = A[i];		for(int i = point[1]; i; i = E[i].nxt)		if (!mark[E[i].to])			P[++tot2] = (data2) {E[i].to, c[E[i].to][0]};		stable_sort(B + 1, B + tot3 + 1);	stable_sort(P + 1, P + tot2 + 1);	//	printf("%d %d\n", tot3, tot2);		if (tot3 < tot2) return false;	for(; tot3 && tot2; --tot3, --tot2)		if (B[tot3].left < P[tot2].dis) return false;	return true;}int main() {	freopen("a.in", "r", stdin);	n = in();	int u, v, w;	for(int i = 1; i < n; ++i) {		u = in(); v = in(); w = in();		ins(u, v, w);		ins(v, u, w);	}		dfs(1);	for(int j = 1; j <= 17; ++j)		for(int i = 1; i <= n; ++i) {			f[i][j] = f[f[i][j - 1]][j - 1];			if (f[i][j]) c[i][j] = c[i][j - 1] + c[f[i][j - 1]][j - 1];		}	m = in();	for(int i = 1; i <= m; ++i) Army[i] = in();	ll left = 0, right = 50000000000000ll, mid;	while (left < right) {		mid = (left + right) >> 1;		if (can(mid)) right = mid;		else left = mid + 1;	}		printf("%lld\n", left);	return 0;}

_(:з」∠)_

【CodeVS 1218】【NOIP 2012】疫情控制