当前位置:首页 >> 学科竞赛 >>

noip2012疫情控制题解


noip2012疫情控制 题解
题目大意
给出一棵 n 个节点的树,根是1,要在除根节点以外的点建立检查点,使得从每条根到 叶子的路径上都至少存在一个检查点。检查点由军队来建立。初始军队的位置是给定的,移 动军队走一条边需要花费这条边的权值的时间。 现在要求一个方案, 移动军队到某个最佳位 置,使得总用时最少。
【数据范围】 保证军队不会驻扎在首都。

对于20%的数据,2≤ n≤ 10; 对于40%的数据,2 ≤n≤50,0<w <105; 对于60%的数据,2 ≤ n≤1000,0<w <106; 对于80%的数据,2 ≤ n≤10,000; 对于100%的数据,2≤m≤n≤50,000,0<w <109。

首先确定思路是二分。 然后关键是怎么 check 每个军队肯定是要尽量往上走的。把军队分为走得到 root 和走不到两种情况。 把仅通过走不到 root 的军队就能控制的第二层的结点去掉,剩下的就需要通过剩下的军队 来控制。 每个军队都要匹配一个结点,排序完直接匹配就可以了。但是这里有一个细节,就是如果一 个军队要控制自己所属的结点,就不需要再额外添加时间。 于是我们可以先按军队剩余时间从小到大排, 再按需要的时间排序没控制的结点, 然后决定 每一个军队控制哪个结点。由于已经排过序了,所以当前军队肯定是最没用的。所以如果他 所属的结点未被控制,就让他去肯定是最好的方案。

还有一个问题。 怎么得出那些结点没被控制?这个有几个方法, 可以用倍增直接暴力把军队 推上去,还有就是用拓扑排序。 这里介绍下拓扑的方法: 对于每一个结点记录所有军队往上走走到这里剩余时间的最大值 time[]。再记一个能 否到达 arr[],如果 time[u] >= 0则 arr[u] = true;如果 u 的所有儿子都可控制,则 arr[u] = true;否则都是 false

然后问题就解决了!时间复杂度 O(n*log2n)

代码

//看完后麻烦帮忙下下来棒忙加点财富。。 。。大家也可以加点人品。。 。。

#include <cstdio> #include <algorithm> #include <cstring> typedef long long ll; const int N = 50000 + 9; int ec,n,q[N],mark[N],army[N],t1[N],t2[N],ance[N],father[N],son[N],m,times; ll dis[N],time[N],cost[N]; bool notleaf[N],arr[N],can_use[N]; struct edge{int next,link,w;}es[N*2]; inline bool cmp1(const int i,const int j){return cost[i] < cost[j];} inline bool cmp2(const int i,const int j){return dis[army[i]] > dis[army[j]];} inline void addedge(const int x,const int y,const int z) { es[++ec].next = son[x]; son[x] = ec; es[ec].link = y; es[ec].w = z; } inline void Addedge(const int x,const int y,const int z){addedge(x,y,z),addedge(y,x,z);} bool check(const ll mid) { ++times; memset(time,-1,sizeof(*time)*(n + 1)); memcpy(arr,notleaf,sizeof(*arr)*(n + 1)); memset(can_use,0,sizeof(*can_use)*(m + 1)); for (int i = n; i; --i) { const int u = q[i]; if (mark[u] && dis[u] > mid) time[u] = mid; if (time[father[u]] < time[u] - cost[u]) time[father[u]] = time[u] - cost[u]; if (time[u] >= 0) arr[u] = true;

if (!arr[u]) arr[father[u]] = false; } for (int i = 1; i <= m; ++i) if (dis[army[i]] <= mid) can_use[i] = true; t1[0] = t2[0] = 0; for (int i = son[1]; i; i = es[i].next) if (!arr[es[i].link]) t1[++t1[0]] = es[i].link; for (int i = 1; i <= m; ++i) if (can_use[i]) t2[++t2[0]] = i; std::sort(t1 + 1,t1 + 1 + t1[0],cmp1); std::sort(t2 + 1,t2 + 1 + t2[0],cmp2); for (int i = 1,j = 1; i <= t2[0]; ++i) { if (!arr[ance[army[t2[i]]]]) arr[ance[army[t2[i]]]] = true; else if (cost[t1[j]] + dis[army[t2[i]]] <= mid) arr[t1[j]] = true; while (j <= t1[0] && arr[t1[j]]) ++j; if (j > t1[0]) return true; } return false; } void BFS(const int s) { int h = 1,t = 0; q[++t] = s; while (h <= t) { const int u = q[h++]; notleaf[u] = false; for (int i = son[u]; i; i = es[i].next) { const int v = es[i].link; if (v == father[u]) continue; dis[v] = dis[u] + es[i].w; father[v] = u; cost[v] = es[i].w; if (u != s) ance[v] = ance[u]; else ance[v] = v; q[++t] = v; notleaf[u] = true; } } } int main() { #ifndef ONLINE_JUDGE freopen("blockade.in","r",stdin);

freopen("blockade.out","w",stdout); #endif scanf("%d",&n); ll r = 1,l = 0,tot = 0; for (int i = 1,x,y,z; i < n; ++i) { scanf("%d%d%d",&x,&y,&z); r += z; Addedge(x,y,z); } tot = r; scanf("%d",&m); for (int i = 1; i <= m; ++i) { scanf("%d",army + i); mark[army[i]] = i; } BFS(1); while (l + 1 < r) { const ll mid = (l + r)/2; if (check(mid)) r = mid; else l = mid; } if (r == tot) puts("-1"); else printf("%I64d\n",r); //check(9); }


相关文章:
noip2012疫情控制题解
noip2012疫情控制 题解题目大意给出一棵 n 个节点的树,根是1,要在除根节点以外的点建立检查点,使得从每条根到 叶子的路径上都至少存在一个检查点。检查点由...
noip 2012 提高组 解题报告
noip 2012 提高组 解题报告_学科竞赛_高中教育_教育专区。noip 2012 提高组 ...疫情控制 DFS+倍增+二分答案+贪心 1. dfs 找出倍增序列 2. 二分答案:在...
Noip2012普及组题解
Noip2012普及组题解_学科竞赛_初中教育_教育专区。noip的题解 质因数分解 (prime.cpp/c/pas) 【问题描述】 已知正整数n是两个不同的质数的乘积,试求出较大...
NOIp06-15题解分析
4.同余方程:裸数学题 5.借教室:二分(或线段树卡常) 6.疫情控制:二分答案+...。其实搜索也能过吧 noip2012 day1 题 1:字符串模拟 题 2:数学推导能力+...
noip2012 开车旅行 题解
noip2012 开车旅行 题解_学科竞赛_高中教育_教育专区。noip2012开车旅行 题解题目大意:给出 n 个排成一行的城市, 每个城市有一个不同的海拔。 定义两个城市间...
NOIP2012普及组复赛解题报告
NOIP2012普及组复赛解题报告_学科竞赛_初中教育_教育专区 暂无评价|0人阅读|0次下载|举报文档 NOIP2012普及组复赛解题报告_学科竞赛_初中教育_教育专区。第一题:...
NOIP2012问题求解题目
[i]) 如果根节点不选,则与根节点无关,直接为左右儿子的相乘,有 g(i)...(计算的时候是从下往上算,这里设树的节点总数为 根节点编号),显然该就是...
NOIP2012普及组初赛试题和参考答案
NOIP2012普及组初赛试题和参考答案_IT认证_资格考试/...而原问题的解就是子问题解的并。 A.动态规划 B....对于每个点,可以控制所有位于它左下方的点(即 x、...
NOIP2012 提高组初赛答案
NOIP2012 提高组初赛答案_学科竞赛_高中教育_教育专区。NOIP2012 提高组初赛答案...NOIP2012提高组初赛试题 暂无评价 19页 1下载券 NOIP2000提高组初赛答案 1页...
NOIP2012提高组复赛试题
NOIP2012提高组复赛试题_学科竞赛_高中教育_教育专区...求关于的同余方程三 1 (mod 句的最小正整数解。...如果无法控制疫情则输出.1。 〖输入输出样例〗 b ...
更多相关标签:
noip2012疫情控制 | noip疫情控制 | noip2012提高组复赛 | 疫情控制 | noip2012普及组复赛 | noip2012开车旅行 | noip2012提高组初赛 | 学校水痘疫情控制措施 |