首页 > 代码库 > 【BZOJ-2286】消耗战 虚树 + 树形DP
【BZOJ-2286】消耗战 虚树 + 树形DP
2286: [Sdoi2011消耗战
Time Limit: 20 Sec Memory Limit: 512 MBSubmit: 2120 Solved: 752
[Submit][Status][Discuss]
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
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
32
22
HINT
对于100%的数据，2<=n<=250000,m>=1,sigma(ki)<=500000,1<=ki<=n-1
Source
Stage2 day2
Solution
虚树+树形DP
先看虚树...
一点个人的理解：
给定的树上有很多节点比较无用，会影响复杂度，所以我们需要把它们的影响降低，那么我们就建出一棵包含所有特殊点的，以及一些必要的LCA的虚树，使得里面的点数尽量的少
大体的构建需要 栈 + LCA + dfs序
首先对给出的树求出dfs序，然后将给出的特殊点按dfs序从小到大排序；
然后用一个栈去维护，退栈和虚树连边是相结合的，这个栈中元素的意义：当前点在原树中到根的路径上在虚树上的点
排序之后，从左到右加点，假设当前要入栈的节点$x$,与当前栈顶LCA为$y$,当$x$被加入后，栈中所有深度>$y$的点需要退栈，这时候就对应连边
一个栗子（转）：
为了方便，假定dfs序和编号是一样的，红色点为特殊点
那么我们模拟一下虚树的构造过程，
首先按照dfs序，我们加入3，此时stack{3}
然后加入5，栈顶为3，它们的LCA为2，这时候开始退栈，发现deep[3]>deep[2]所以把3退栈，这时候2-->3连边
然后2入栈，此时stack{2}
然后5入栈，此时stack{2,5}
然后考虑6，栈顶为5，它们的LCA为2，这时候开始退栈，发现deep[5]>deep[2]那么把5退栈，这时候2-->5连边
然后考虑2入栈，发现栈顶为2，那么2不入栈
然后5入栈，此时stack{2,6}
依次退栈2-->6连边。
大体的建树操作：
bool cmp(int x,int y) {return dfn[x]<dfn[y];}struct RoadNode{int next,to;}road[MAXN<<1];int last[MAXN],tot;void AddRoad(int u,int v) {tot++; road[tot].next=last[u]; last[u]=tot; road[tot].to=v;}void InsertRoad(int u,int v) {if (u==v) return; AddRoad(u,v);}int a[MAXN],tp,st[MAXN],top;void MakeTree(int K){ tot=0; sort(a+1,a+K+1,cmp); tp=0; a[++tp]=a[1]; for (int i=2; i<=K; i++) if (LCA(a[tp],a[i])!=a[tp]) a[++tp]=a[i]; st[++top]=1; for (int i=1; i<=tp; i++) { int now=a[i],lca=LCA(now,st[top]); while (top) { if (deep[lca]>=deep[st[top-1]]) { InsertRoad(lca,st[top--]); if (st[top]!=lca) st[++top]=lca; break; } InsertRoad(st[top-1],st[top]); top--; } if (st[top]!=now) st[++top]=now; } while (--top) InsertRoad(st[top],st[top+1]);}
这道题就是建出虚树，然后再虚树上进行DP，这道题是简单DP，就不细说了
Code
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>using namespace std;int read(){ int x=0,f=1; char ch=getchar(); while (ch<‘0‘ || ch>‘9‘) {if (ch==‘-‘) f=-1; ch=getchar();} while (ch>=‘0‘ && ch<=‘9‘) {x=x*10+ch-‘0‘; ch=getchar();} return x*f;}#define MAXN 300010#define LL long longint N,M,K;struct EdgeNode{int next,to,val;}edge[MAXN<<1];int head[MAXN],cnt;void AddEdge(int u,int v,int w) {cnt++; edge[cnt].next=head[u]; head[u]=cnt; edge[cnt].to=v; edge[cnt].val=w;}void InsertEdge(int u,int v,int w) {AddEdge(u,v,w); AddEdge(v,u,w);}int deep[MAXN],dfn[MAXN],father[MAXN][21],t;LL minn[MAXN];void DFS(int now,int last){ dfn[now]=++t; for (int i=1; i<=20; i++) if (deep[now]>=(1<<i)) father[now][i]=father[father[now][i-1]][i-1]; else break; for (int i=head[now]; i; i=edge[i].next) if (edge[i].to!=last) { minn[edge[i].to]=min(minn[now],(LL)edge[i].val); deep[edge[i].to]=deep[now]+1; father[edge[i].to][0]=now; DFS(edge[i].to,now); }}int LCA(int x,int y){ if (deep[x]<deep[y]) swap(x,y); int dd=deep[x]-deep[y]; for (int i=0; i<=20; i++) if (dd&(1<<i)) x=father[x][i]; for (int i=20; i>=0; i--) if (father[x][i]!=father[y][i]) x=father[x][i],y=father[y][i]; if (x==y) return x; else return father[x][0];}bool cmp(int x,int y) {return dfn[x]<dfn[y];}struct RoadNode{int next,to;}road[MAXN<<1];int last[MAXN],tot;void AddRoad(int u,int v) {tot++; road[tot].next=last[u]; last[u]=tot; road[tot].to=v;}void InsertRoad(int u,int v) {if (u==v) return; AddRoad(u,v);}int a[MAXN],tp,st[MAXN],top;void MakeTree(int K){ tot=0; sort(a+1,a+K+1,cmp); tp=0; a[++tp]=a[1]; for (int i=2; i<=K; i++) if (LCA(a[tp],a[i])!=a[tp]) a[++tp]=a[i]; st[++top]=1; for (int i=1; i<=tp; i++) { int now=a[i],lca=LCA(now,st[top]); while (top) { if (deep[lca]>=deep[st[top-1]]) { InsertRoad(lca,st[top--]); if (st[top]!=lca) st[++top]=lca; break; } InsertRoad(st[top-1],st[top]); top--; } if (st[top]!=now) st[++top]=now; } while (--top) InsertRoad(st[top],st[top+1]);}LL f[MAXN];void DP(int now){ f[now]=minn[now]; LL tmp=0; for (int i=last[now]; i; i=road[i].next) DP(road[i].to),tmp+=f[road[i].to]; last[now]=0; if (tmp==0) f[now]=minn[now]; else f[now]=min(tmp,f[now]);}int main(){ N=read(); for (int x,y,z,i=1; i<=N-1; i++) x=read(),y=read(),z=read(),InsertEdge(x,y,z); minn[1]=1LL<<60; DFS(1,0); M=read(); while (M--) { K=read(); for (int i=1; i<=K; i++) a[i]=read(); MakeTree(K); DP(1); printf("%lld\n",f[1]); } return 0;}
【BZOJ-2286】消耗战 虚树 + 树形DP
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。