首页 > 代码库 > 【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】疫情控制
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。