题目链接

观察题目,答案明显具有单调性。

因为如果用$x$小时能够控制疫情,那么用$(x+1)$小时也一定能控制疫情。

由此想到二分答案,将问题转换为判断用$x$小时是否能控制疫情。

对于那些在$x$小时内不能够走到根节点的子节点上的军队,让他们尽量往上走即可,走到哪里是哪里,这样显然不会更劣。

对于那些在$x$小时内能走到根节点的子节点上的军队,就让他们先走到根节点的子节点上。

然后搞搞贪心即可。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<fstream>
using namespace std;
struct edge
{
int last;
int end;
int weight;
}e[100005];
int n=0,m=0,ne=0;
int a[50005],note[50005],f[50005][20];
bool c[50005];
long long k1[50005],k2[50005],dis[50005];
vector<int> s[50005];
void NewEdge(int u,int v,int w)
{
ne++;
e[ne].last=note[u];
e[ne].end=v;
e[ne].weight=w;
note[u]=ne;
}
void dfs(int x,int fx)
{
for(int i=note[x];i;i=e[i].last)
if(e[i].end!=fx)
{
dis[e[i].end]=dis[x]+e[i].weight;
f[e[i].end][0]=x;
dfs(e[i].end,x);
}
}
void calc()
{
for(int j=1;j<=16;j++)
for(int i=1;i<=n;i++)
f[i][j]=f[f[i][j-1]][j-1];
}
bool dfss(int x,int fx)
{
if(c[x]) return false;
bool flag=false;
for(int i=note[x];i;i=e[i].last)
if(e[i].end!=fx)
{
flag=true;
if(dfss(e[i].end,x)) return true;
}
if(!flag) return true;
return false;
}
bool check(long long x)
{
for(int i=1;i<=n;i++)
c[i]=false,s[i].clear();
for(int i=1;i<=m;i++)
{
int y=a[i];
long long w=0;
for(int j=16;j>=0;j--)
if(f[y][j]>1&&w+dis[y]-dis[f[y][j]]<=x)
w+=dis[y]-dis[f[y][j]],y=f[y][j];
if(f[y][0]==1) s[y].push_back(a[i]);
c[y]=true;
}
int cnt1=0,cnt2=0;
for(int i=note[1];i;i=e[i].last)
{
bool h=c[e[i].end];
c[e[i].end]=false;
bool t=dfss(e[i].end,1);
c[e[i].end]=h;
int len=s[e[i].end].size();
for(int j=0;j<len;j++)
{
if(t&&dis[s[e[i].end][j]]+e[i].weight>x)
{t=false;continue;}
k1[++cnt1]=x-dis[s[e[i].end][j]];
}
if(t) k2[++cnt2]=e[i].weight;
}
sort(k1+1,k1+cnt1+1);
sort(k2+1,k2+cnt2+1);
for(int i=1,j=1;i<=cnt2;i++)
{
while(j<=cnt1&&k1[j]<k2[i]) j++;
if(j>cnt1) return false;
j++;
}
return true;
}
int main()
{
scanf("%d",&n);
long long hi=0;
for(int i=1;i<=n-1;i++)
{
int u=0,v=0,w=0;
scanf("%d%d%d",&u,&v,&w),hi+=w;
NewEdge(u,v,w);
NewEdge(v,u,w);
}
scanf("%d",&m);
for(int i=1;i<=m;i++) scanf("%d",&a[i]);
dfs(1,0),calc();
long long l=-1,r=hi;
while(l+1<r)
{
long long mid=(l+r)>>1;
if(check(mid)) r=mid;
else l=mid;
}
if(!check(r)) printf("-1");
else printf("%lld",r);
return 0;
}

Luogu P1084

最新文章

  1. 利用mysql查询总数据条数,再php处理数据转出数组,生成随机返回到页面,可以做成刷新页面,出现不同的内容
  2. 实验三 组合逻辑电路的VHDL设计
  3. Redis数据导入工具优化过程总结
  4. OpenHCI - Data Transfer Types
  5. DB2分区表删除和添加分区
  6. 《Pro Git》学习笔记
  7. Java数学表示式解析工具- jeval
  8. 【Linux常用命令(更新)】
  9. CF615D Multipliers [数学]
  10. 一些神奇的JS功效
  11. Java for Anfroid 学习之 内部类
  12. oracle初试、函数、增删改查、多表查询
  13. 使用HTML5拍照
  14. phpmock测试
  15. passwd命令
  16. Confluence 6 设置其他页面为你空间的主页
  17. eclipse在server中tomcat server找不到的问题
  18. github与git基本操作(一)
  19. 20155213 《网络攻防》 Exp1 PC平台逆向破解
  20. hdu 1007 N个点中输出2点的最小距离的一半

热门文章

  1. go语言游戏服务端开发(三)——服务机制
  2. Django学习day03随堂笔记
  3. Spring Cloud Hystrix 学习(三)请求合并
  4. 一生挚友redo log、binlog《死磕MySQL系列 二》
  5. golang 开发环境 配置 go语言 liteIDE
  6. Go语言之循环与条件判断
  7. 开源框架 - 新 代码生成器 WebFirst / .NET Core
  8. 数据库MHA故障分析
  9. 题解 51nod 1597 有限背包计数问题
  10. js--标签语法的使用