BZOJ2286:[SDOI2011]消耗战(树形DP,虚树)

BZOJ2286:[SDOI2011]消耗战(树形DP,虚树)

Description

在一场战争中,战场由n个岛屿和n-1个桥梁组成,保证每两个岛屿间有且仅有一条路径可达。现在,我军已经侦查到敌军的总部在编号为1的岛屿,而且他们已经没有足够多的能源维系战斗,我军胜利在望。已知在其他k个岛屿上有丰富能源,为了防止敌军获取能源,我军的任务是炸毁一些桥梁,使得敌军不能到达任何能源丰富的岛屿。由于不同桥梁的材质和结构不同,所以炸毁不同的桥梁有不同的代价,我军希望在满足目标的同时使得总代价最小。
侦查部门还发现,敌军有一台神秘机器。即使我军切断所有能源之后,他们也可以用那台机器。机器产生的效果不仅仅会修复所有我军炸毁的桥梁,而且会重新随机资源分布(但可以保证的是,资源不会分布到1号岛屿上)。不过侦查部门还发现了这台机器只能够使用m次,所以我们只需要把每次任务完成即可。

Input

第一行一个整数n,代表岛屿数量。

接下来n-1行,每行三个整数u,v,w,代表u号岛屿和v号岛屿由一条代价为c的桥梁直接相连,保证1<=u,v<=n且1<=c<=100000。

第n+1行,一个整数m,代表敌方机器能使用的次数。

接下来m行,每行一个整数ki,代表第i次后,有ki个岛屿资源丰富,接下来k个整数h1,h2,…hk,表示资源丰富岛屿的编号。

Output

输出有m行,分别代表每次任务的最小代价。

Sample Input

10

1 5 13

1 9 6

2 1 19

2 4 8

2 3 91

5 6 8

7 5 4

7 8 31

10 7 9

3

2 10 6

4 5 7 8 3

3 9 4 6

Sample Output

12

32

22

HINT

对于100%的数据,2<=n<=250000,m>=1,sigma(ki)<=500000,1<=ki<=n-1

Solution

虚树真是个好东西啊QAQ

推荐博客

建议对虚树的理解看第一个,构建看第二个QAQ

题解去看第二个吧我也懒得写了XD

顺带提一句因为本题特殊,所以建虚树的时候要写成57行那样,否则就把57行删掉改成58行就行了。

至于本题为什么要像57行那么写呢……

假设$x$点是$y$的祖先,如果$x$到根不连通,那么$y$到根一定不连通,所以$y$点也就没有加进去的必要了。而且加进去的话像我这样$DP$也就不对了啊啊QAQQQQ

Code

 1 #include<iostream>  2 #include<cstring>  3 #include<cstdio>  4 #include<algorithm>  5 #include<vector>  6 #define N (250009)  7 #define LL long long  8 using namespace std;  9  10 struct Edge{ int to,next,len;}edge[N<<1];  11 int n,m,k,u,v,l,dfs_num;  12 int a[N],Depth[N],f[N][19],DFN[N];  13 LL Min[N];  14 int head[N],num_edge;  15  16 void add(int u,int v,int l)  17 {  18 edge[++num_edge].to=v;  19 edge[num_edge].next=head[u];  20 edge[num_edge].len=l;  21 head[u]=num_edge;  22 }  23  24 void DFS(int x,int fa)  25 {  26 f[x][0]=fa;  27 for (int i=1; i<=18; ++i) f[x][i]=f[f[x][i-1]][i-1];  28 DFN[x]=++dfs_num; Depth[x]=Depth[fa]+1;  29 for (int i=head[x]; i; i=edge[i].next)  30 if (edge[i].to!=fa)  31  {  32 Min[edge[i].to]=min(Min[x],(LL)edge[i].len);  33  DFS(edge[i].to,x);  34  }  35 }  36  37 int LCA(int x,int y)  38 {  39 if (Depth[x]<Depth[y]) swap(x,y);  40 for (int i=18; i>=0; --i)  41 if (Depth[f[x][i]]>=Depth[y]) x=f[x][i];  42 if (x==y) return x;  43 for (int i=18; i>=0; --i)  44 if (f[x][i]!=f[y][i]) x=f[x][i], y=f[y][i];  45 return f[x][0];  46 }  47  48 vector<int>E[N];  49 void ADD(int x,int y) {E[x].push_back(y);}  50 int stack[N],top;  51 bool cmp(int x,int y) { return DFN[x]<DFN[y];}  52  53 void Insert(int x)  54 {  55 if (top==1) {stack[++top]=x; return;}  56 int lca=LCA(x,stack[top]);  57 if (lca==stack[top]) return;  58 // if (lca==stack[top]) {stack[++top]=x; return;}  59 while (top>1 && DFN[stack[top-1]]>=DFN[lca])  60 ADD(stack[top-1],stack[top]), top--;  61 if (lca!=stack[top]) ADD(lca,stack[top]), stack[top]=lca;  62 stack[++top]=x;  63 }  64  65 void Build()  66 {  67 stack[top=1]=1;  68 for (int i=1; i<=k; ++i) Insert(a[i]);  69 while (top>=2) ADD(stack[top-1],stack[top]), top--;  70 }  71  72 LL DP(int x)  73 {  74 int sz=E[x].size();  75 if (!sz) return Min[x];  76 LL ans=0;  77 for (int i=0; i<sz; ++i)  78 ans+=DP(E[x][i]);  79  E[x].clear();  80 return min(ans,Min[x]);  81 }  82  83 int main()  84 {  85 Min[1]=1e18;  86 scanf("%d",&n);  87 for (int i=1; i<=n-1; ++i)  88  {  89 scanf("%d%d%d",&u,&v,&l);  90  add(u,v,l); add(v,u,l);  91  }  92 DFS(1,0);  93 scanf("%d",&m);  94 for (int i=1; i<=m; ++i)  95  {  96 scanf("%d",&k);  97 for (int j=1; j<=k; ++j) scanf("%d",&a[j]);  98 sort(a+1,a+k+1,cmp);  99  Build(); 100 printf("%lld\n",DP(1)); 101  } 102 }

转载于:https://www.cnblogs.com/refun/p/10064045.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/101285.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 大屏数据可视化案例「建议收藏」

    大屏数据可视化案例「建议收藏」数据可视化:把相对复杂的、抽象的数据通过可视的、交互的方式进行展示,从而形象直观地表达数据蕴含的信息和规律。数据可视化是数据空间到图形空间的映射,是抽象数据的具象表达。数据可视化交互的基本原则:总览为先,缩放过滤按需查看细节。大屏数据可视化是当前可视化领域的一项热门应用,通常可以分为信息展示类、数据分析类及监控预警类。大屏数据可视化应用的难点并不在于图表类型的多样化,而在于如何能在…

  • fscanf()函数具体解释

    fscanf()函数具体解释

    2021年12月15日
  • win10更改pip源方法

    win10更改pip源方法win10更改pip源win10安装TensorFlow卡崩具体做法win10安装TensorFlow卡崩更改为国内清华大学镜像源,即可。具体做法在c:\user(或者用户)\电脑的用户名\,目录下创建一个命名为“pip”的文件夹(如:C:\Users\Administrator\pip),在该文件夹下创建一个命名为“pip.ini”的文件,在该文件中写入以下内容:[global]in…

  • Qt-4.8.7交叉编译平台的搭建、移植详解( aarch32、aarch64 、mips64)「建议收藏」

    Qt-4.8.7交叉编译平台的搭建、移植详解( aarch32、aarch64 、mips64)「建议收藏」由于项目需要,需要在国产系统(银河麒麟系统–飞腾cpu-arm64)上用firefox加载一个npapi插件,而firefox是一个32位的浏览器,而银河麒麟系统不支持编译32位的动态库,因此只能用交叉编译环境来编译arm32的动态库。整了一个星期的Qt移植,今天终于弄出来了。网上的移植教程很多,可没有一篇能够完整编译出自己需要的版本,因此记录一下学习过程以及编译…

  • PCR雷达传感器感应_倒车雷达传感器在哪里

    PCR雷达传感器感应_倒车雷达传感器在哪里一.设备唤醒i》检测人靠近设备ii》无视穿越的人员iii》可做手势识别应用场景:智能音箱;笔记本;广告机;投影仪;灯具;控制面板开关独特算法:1》 检测静止不动的人员,内置检测人的呼吸信号。图示为雷达传感器抓取人呼吸的信号在0.3-0.35hz效果。2》 可过滤快速移动物体干扰,内置仅对慢速移动检测,图示效果为雷达传感器过滤风扇对测试的影响。二.车内人员检测欧洲新车评估计划(EuroNCAP)计划在2022年将儿童存在检测纳入全面评级。测试评估分析:1岁婴儿睡在儿童保护座椅上

  • onshow和onload区别

    onshow和onload区别onshow在每次打开页面都会加载数据,可以用于数据在需要刷新的环境下onload只是在第一次进入页面会刷新数据,从二级页面回来不会重新加载数据

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号