luogu1084 疫情控制

luogu1084 疫情控制

​​题目描述

H 国有 n 个城市，这 n 个城市用 n-1 条双向道路相互连通构成一棵树，1 号城市是首都，也是树中的根节点。

H 国的首都爆发了一种危害性极高的传染病。当局为了控制疫情，不让疫情扩散到边境城市（叶子节点所表示的城市），决定动用军队在一些城市建立检查点，使得从首都到边境城市的每一条路径上都至少有一个检查点，边境城市也可以建立检查点。但特别要注意的是，首都是不能建立检查点的。

现在，在 H 国的一些城市中已经驻扎有军队，且一个城市可以驻扎多个军队。一支军队可以在有道路连接的城市间移动，并在除首都以外的任意一个城市建立检查点，且只能在一个城市建立检查点。一支军队经过一条道路从一个城市移动到另一个城市所需要的时间等于道路的长度（单位：小时）。

请问最少需要多少个小时才能控制疫情。注意：不同的军队可以同时移动。

输入输出格式

输入格式：

第一行一个整数 n，表示城市个数。

接下来的 n-1 行，每行 3 个整数，u、v、w，每两个整数之间用一个空格隔开，表示从城市 u 到城市 v 有一条长为 w 的道路。数据保证输入的是一棵树，且根节点编号为 1。

接下来一行一个整数 m，表示军队个数。

接下来一行 m 个整数，每两个整数之间用一个空格隔开，分别表示这 m 个军队所驻扎的城市的编号。

输出格式：

共一行，包含一个整数，表示控制疫情所需要的最少时间。如果无法控制疫情则输出-1。

输入输出样例

输入样例#1：

4 1 2 1 1 3 2 3 4 3 2 2 2 输出样例#1：

3 说明

【输入输出样例说明】

第一支军队在 2 号点设立检查点，第二支军队从 2 号点移动到 3 号点设立检查点，所需时间为 3 个小时。

【数据范围】

保证军队不会驻扎在首都。

对于 20%的数据，2≤ n≤ 10；

对于 40%的数据，2 ≤n≤50，0

对于 60%的数据，2 ≤ n≤1000，0

对于 80%的数据，2 ≤ n≤10,000；

对于 100%的数据，2≤m≤n≤50,000，0

NOIP 2012 提高组 第二天 第三题

数据可能有点水，我忘了写-1的情况也就是 当我军队数比1号节点的孩子要少的话就是-1

那么我们可以用二分答案的方法 确定我们的答案是什么的

我们首先二分一个答案然后如何验证呢？

我们求出所有军队到1需要的时间 然后规定时间内能到1的军队我们让他在1待命，并且求出他还能剩余的行动时间 要是规定时间内无法到1的军队，就让它停在那里，然后做好标记，

后面我们再搜索一遍 确定哪些节点（边境城市）还没有军队 我们还有一个策略就是 如果这个军队上到1号节点 并且他的剩余时间不足够返回自己上来的那棵和根连接的子树的时候就 不如让他回去

不要上到根节点来

然后贪心的让剩余时间最大的去做最长的 这个做最长的就是1号节点到深度比他大一的那个节点就可以了

注意pair的使用要是忘了写first或者second也不会报错，但是答案可能会不对…

#include#include#include#define N 55000#define ll long long#define pa pairusing namespace std;inline int read(){ int x=0;char ch=getchar(); while (ch<'0'||ch>'9') ch=getchar(); while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();} return x;}struct node{ int y,z,next;}data[N<<1];int fa[N][18],dep[N],n,m,army[N],b[N],Log[N],h[N],num;ll dis[N][18];bool mark[N],used[N];void dfs1(int x,int top){ for (int i=h[x];i;i=data[i].next){ int y=data[i].y,z=data[i].z;if(x!=1)b[x]=top; if (fa[x][0]==y) continue; fa[y][0]=x;dis[y][0]=z;dep[y]=dep[x]+1; for (int j=1;j<=Log[dep[y]];++j){ fa[y][j]=fa[fa[y][j-1]][j-1]; dis[y][j]=dis[y][j-1]+dis[fa[y][j-1]][j-1]; } if (fa[y][0]==1) dfs1(y,y);else dfs1(y,top); }}void dfs2(int x){ bool flag=true,son_exist=false; for (int i=h[x];i;i=data[i].next){ int y=data[i].y; if (fa[x][0]==y) continue;son_exist=true; dfs2(y);if (!mark[y]) flag=false; } if (flag&&son_exist) mark[x]=true;}pa q1[N],q2[N];inline bool judge(ll tot){ int top1=0,top2=0;memset(mark,0,sizeof(mark));memset(used,0,sizeof(used)); for (int i=1;i<=m;++i){ int x=army[i];ll disx=0; for (int j=Log[n];j>=0;--j){ if (fa[x][j]&&disx+dis[x][j]<=tot){ disx+=dis[x][j];x=fa[x][j]; } } if (x==1) q1[++top1]=make_pair(tot-disx,b[army[i]]);else mark[x]=true; }dfs2(1);if (mark[1]) return true; for (int i=h[1];i;i=data[i].next){ int y=data[i].y;if (mark[y]) continue; q2[++top2]=make_pair(dis[y][0],y); } sort(q1+1,q1+top1+1);sort(q2+1,q2+top2+1); //如果去根了，然后发现自己后继无人，自己剩余的时间又不够回去的干脆就留在儿子那里的 for (int i=1;i<=top1;++i){ int y=q1[i].second;ll rest=q1[i].first; if (!mark[y]&&rest=q2[q2_pointer].first) ++q1_pointer,++q2_pointer;else ++q1_pointer; } while (q2_pointer<=top2&&mark[q2[q2_pointer].second])++q2_pointer; if (q2_pointer==top2+1) return true;else return false;}int main(){ freopen("1084.in","r",stdin); n=read(); for (int i=1;i>1]+1; dfs1(1,0);m=read(); for (int i=1;i<=m;++i) army[i]=read(); ll l=0,r=500000; while (l<=r){ ll mid=l+r>>1; if (judge(mid)) r=mid-1;else l=mid+1; } printf("%lld",l); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。