luoguP1084 疫情控制 题目

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define il inline
#define rg register
#define ll long long
#define N 60000
#define inf 2147483647
using namespace std; int n,m,hd[N],cnt,u,v,w;
int c,idx[N];
int le,ri=;
int dis[N][],up[N][];
int ok[N],use[N],vis[N];
struct S{
int res,idx;
}ne[N],to[N];
struct T{
int nt,to,w;
}edge[N<<];
il void re(rg int &x);
void add(rg int fm,rg int to,rg int w);
void ST(rg int i,rg int fa);
int check(rg int lim);
int Dfs(rg int u,rg int fa);
int Cmp(const S &x,const S &y); int main()
{
re(n);
for(rg int i=;i<n;++i)
{
re(u),re(v),re(w);
add(u,v,w),add(v,u,w);
if(u==||v==)c++;
}
re(m);
if(m<c){cout<<-;return ;}
for(rg int i=;i<=m;++i)
re(idx[i]); ST(,);
for(rg int k=;k<=;++k)
{
for(rg int i=;i<=n;++i)
{
up[i][k]=up[up[i][k-]][k-];
dis[i][k]=dis[up[i][k-]][k-]+dis[i][k-];
}
}
while(le<ri)
{
rg int mid=((le+ri)>>);
if(check(mid))ri=mid;
else le=mid+;
}
cout<<le; return ;
} il void re(rg int &x)
{
rg int res=;rg int w=;char c=getchar();
while((c<''||c>'')&&c!='-')c=getchar();
if(c=='-')w=-,c=getchar();
while(c>=''&&c<='')res=(res<<)+(res<<)+c-'',c=getchar();
x=w*res;
}
void add(rg int fm,rg int to,rg int w)
{
edge[++cnt].nt=hd[fm];
edge[cnt].to=to;
edge[cnt].w=w;
hd[fm]=cnt;
}
void ST(rg int i,rg int fa)
{
up[i][]=fa;
for(rg int k=hd[i];k;k=edge[k].nt)
{
rg int qw=edge[k].to;
if(qw==fa)continue;
dis[qw][]=edge[k].w;
ST(qw,i);
}
}
int check(rg int lim){
memset(ok,,sizeof(ok));
memset(use,,sizeof(use));
memset(vis,,sizeof(vis));
rg int cnt1=,cnt2=;
rg int top=;
for(rg int i=;i<=m;++i){
rg int res=lim,u=idx[i];
for(rg int k=;k>=;--k){
if(up[u][k]&&up[u][k]!=&&res>=dis[u][k])
res-=dis[u][k],u=up[u][k];
}
if(up[u][]==&&res>dis[u][])
{
to[++cnt1].res=res-dis[u][];
to[cnt1].idx=u;
}
else ok[u]=;
}
Dfs(,);
for(rg int k=hd[];k;k=edge[k].nt){
rg int qw=edge[k].to;
if(!ok[qw]){
ne[++cnt2].res=dis[qw][];
ne[cnt2].idx=qw;
}
}
sort(to+,to+cnt1+,Cmp);
sort(ne+,ne+cnt2+,Cmp);
if(cnt1<cnt2)return ;
for(rg int i=;i<=cnt1;++i)
{
if(!vis[to[i].idx])
{
vis[to[i].idx]=;
continue;
}
while(vis[ne[top].idx])top++;
if(to[i].res>=ne[top].res)
{
vis[ne[top].idx]=,top++;
continue;
}
if(top>cnt2)break;
}
while(vis[ne[top].idx])top++;
if(top<=cnt2)return ;
return ;
}
int Dfs(rg int u,rg int fa)
{
rg int temp=,flag=;
for(rg int k=hd[u];k;k=edge[k].nt)
{
rg int qw=edge[k].to;
if(qw==fa)continue;
flag++,temp&=Dfs(qw,u);
}
if(!flag)temp=;
ok[u]=(ok[u]|temp);
if(ok[u]&&up[u][]==)
vis[u]=;
return ok[u];
}
int Cmp(const S &x,const S &y){return x.res<y.res;}

最新文章

  1. Mac AppleScript 自动完成按键
  2. Android 弹出对话框Dialog充满屏幕宽度
  3. Zabbix自带模板监控MySQL
  4. VISUAL STUDIO 调试
  5. Redis 发布/订阅机制原理分析
  6. MeepoPS——轻量级 Socket 服务
  7. SQL Server 读取CSV中的数据
  8. 关于在Eclipse里面启动了服务,但是localhost:8080无法访问的问题:
  9. 求最大值最小值的方法 时间复杂度O(n)
  10. SICIP-1.3-Defining a new function
  11. LCD显示GPS时钟[嵌入式系统]
  12. Linux(Ubuntu)使用日记------Mongodb的安装与使用
  13. Windows下return,exit和ExitProcess的区别和分析
  14. 【原创 Hadoop&amp;Spark 动手实践 12】Spark MLLib 基础、应用与信用卡欺诈检测系统动手实践
  15. Java技术开发中的坑
  16. C# 实现写入文本文件内容功能
  17. TeeChart入门
  18. MySQL数据库中的字段类型varchar和char的主要区别是什么?哪种字段查找效率要高?
  19. Linux 关机 休眠, 关闭移动设备自动挂载 命令
  20. PHP开发之环境配置

热门文章

  1. asp.net ajax的使用
  2. springcloud费话之断路器(hystrix in feign)
  3. 使用easyui框架 设置时间格式
  4. Springboot2.x整合SpringSecurity
  5. webstorm2018
  6. 快速的统计千万级别uv
  7. linux安装jdk环境(多种方式)
  8. Linux 进程通信之:内存共享(Shared Memory)(转,好文章)
  9. 12.整合neo4j
  10. idea 离线安装 lombok插件