【BZOJ2286】消耗戰(zhàn)（虛樹，動態(tài)規(guī)劃）
題面
BZOJ
Description
在一場戰(zhàn)爭中，戰(zhàn)場由n個島嶼和n-1個橋梁組成，保證每兩個島嶼間有且僅有一條路徑可達(dá)?，F(xiàn)在，我軍已經(jīng)偵查到敵軍的總部在編號為1的島嶼，而且他們已經(jīng)沒有足夠多的能源維系戰(zhàn)斗，我軍勝利在望。已知在其他k個島嶼上有豐富能源，為了防止敵軍獲取能源，我軍的任務(wù)是炸毀一些橋梁，使得敵軍不能到達(dá)任何能源豐富的島嶼。由于不同橋梁的材質(zhì)和結(jié)構(gòu)不同，所以炸毀不同的橋梁有不同的代價，我軍希望在滿足目標(biāo)的同時使得總代價最小。
偵查部門還發(fā)現(xiàn)，敵軍有一臺神秘機(jī)器。即使我軍切斷所有能源之后，他們也可以用那臺機(jī)器。機(jī)器產(chǎn)生的效果不僅僅會修復(fù)所有我軍炸毀的橋梁，而且會重新隨機(jī)資源分布（但可以保證的是，資源不會分布到1號島嶼上）。不過偵查部門還發(fā)現(xiàn)了這臺機(jī)器只能夠使用m次，所以我們只需要把每次任務(wù)完成即可。
第一行一個整數(shù)n，代表島嶼數(shù)量。
接下來n-1行，每行三個整數(shù)u,v,w，代表u號島嶼和v號島嶼由一條代價為c的橋梁直接相連，保證1<=u,v<=n且1<=c<=100000。
第n+1行，一個整數(shù)m，代表敵方機(jī)器能使用的次數(shù)。
接下來m行，每行一個整數(shù)ki，代表第i次后，有ki個島嶼資源豐富，接下來k個整數(shù)h1,h2,…h(huán)k，表示資源豐富島嶼的編號。
Output
輸出有m行，分別代表每次任務(wù)的最小代價。
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%的數(shù)據(jù)，2<=n<=250000,m>=1,sigma(ki)<=500000,1<=ki<=n-1
題解
裸的虛樹\(dp\)
構(gòu)建出虛樹之后直接做\(dp\)就好了
設(shè)\(f[i]\)表示割掉以\(i\)為根的所有子樹中關(guān)鍵點的最小代價
預(yù)處理每個點到根節(jié)點的最短的那條邊長度\(val[i]\)，這樣轉(zhuǎn)移會方便很多
\(f[i]=min(val[i],\sum f[v])\)
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define ll long long
#define RG register
#define MAX 300000
inline int read()
{RG int x=0,t=1;RG char ch=getchar();while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();if(ch=='-')t=-1,ch=getchar();while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();return x*t;
}
struct Line{int v,next,w;}e[MAX<<1];
int h[MAX],cnt=1;
inline void Add(int u,int v,int w){e[cnt]=(Line){v,h[u],w};h[u]=cnt++;}
int fa[MAX],dep[MAX],size[MAX],hson[MAX],dfn[MAX],low[MAX],top[MAX],tim;
int p[MAX<<1],S[MAX];
ll val[MAX];
bool vis[MAX];
int n,m,K;
void dfs1(int u,int ff)
{fa[u]=ff;dep[u]=dep[ff]+1;size[u]=1;for(int i=h[u];i;i=e[i].next){int v=e[i].v;if(v==ff)continue;val[v]=min(val[u],(ll)e[i].w);dfs1(v,u);size[u]+=size[v];if(size[v]>size[hson[u]])hson[u]=v;}
}
void dfs2(int u,int tp)
{top[u]=tp;dfn[u]=++tim;if(hson[u])dfs2(hson[u],tp);for(int i=h[u];i;i=e[i].next){int v=e[i].v;if(v==hson[u]||v==fa[u])continue;dfs2(v,v);}low[u]=tim;
}
int LCA(int u,int v)
{while(top[u]^top[v])(dep[top[u]]<dep[top[v]])?v=fa[top[v]]:u=fa[top[u]];return dep[u]<dep[v]?u:v;
}
bool cmp(int u,int v){return dfn[u]<dfn[v];}
ll DP(int u)
{if(vis[u])return (ll)val[u];ll ret=0;for(int i=h[u];i;i=e[i].next)ret+=DP(e[i].v);return min(ret,(ll)val[u]);
}
int main()
{n=read();for(int i=1;i<n;++i){int u=read(),v=read(),w=read();Add(u,v,w);Add(v,u,w);}val[1]=2e18;dfs1(1,0);dfs2(1,1);memset(h,0,sizeof(h));m=read();while(m--){K=read();cnt=1;for(int i=1;i<=K;++i)vis[p[i]=read()]=true;sort(&p[1],&p[K+1],cmp);for(int i=K;i>1;--i)p[++K]=LCA(p[i],p[i-1]);p[++K]=1;sort(&p[1],&p[K+1],cmp);K=unique(&p[1],&p[K+1])-p-1;for(int i=1,top=0;i<=K;++i){while(top&&low[S[top]]<dfn[p[i]])--top;Add(S[top],p[i],0);S[++top]=p[i];}printf("%lld\n",DP(1));for(int i=1;i<=K;++i)vis[p[i]]=false,h[p[i]]=0;}return 0;
}
轉(zhuǎn)載于:https://www.cnblogs.com/cjyyb/p/9066310.html
總結(jié)
以上是生活随笔為你收集整理的【BZOJ2286】消耗战（虚树，动态规划）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
