題目：

Description

在一場(chǎng)戰(zhàn)爭(zhēng)中，戰(zhàn)場(chǎng)由n個(gè)島嶼和n-1個(gè)橋梁組成，保證每?jī)蓚€(gè)島嶼間有且僅有一條路徑可達(dá)。現(xiàn)在，我軍已經(jīng)偵查到敵軍的總部在編號(hào)為1的島嶼，而且他們已經(jīng)沒有足夠多的能源維系戰(zhàn)斗，我軍勝利在望。已知在其他k個(gè)島嶼上有豐富能源，為了防止敵軍獲取能源，我軍的任務(wù)是炸毀一些橋梁，使得敵軍不能到達(dá)任何能源豐富的島嶼。由于不同橋梁的材質(zhì)和結(jié)構(gòu)不同，所以炸毀不同的橋梁有不同的代價(jià)，我軍希望在滿足目標(biāo)的同時(shí)使得總代價(jià)最小。 偵查部門還發(fā)現(xiàn)，敵軍有一臺(tái)神秘機(jī)器。即使我軍切斷所有能源之后，他們也可以用那臺(tái)機(jī)器。機(jī)器產(chǎn)生的效果不僅僅會(huì)修復(fù)所有我軍炸毀的橋梁，而且會(huì)重新隨機(jī)資源分布（但可以保證的是，資源不會(huì)分布到1號(hào)島嶼上）。不過偵查部門還發(fā)現(xiàn)了這臺(tái)機(jī)器只能夠使用m次，所以我們只需要把每次任務(wù)完成即可。

Input

第一行一個(gè)整數(shù)n，代表島嶼數(shù)量。

接下來n-1行，每行三個(gè)整數(shù)u,v,w，代表u號(hào)島嶼和v號(hào)島嶼由一條代價(jià)為c的橋梁直接相連，保證1<=u,v<=n且1<=c<=100000。

第n+1行，一個(gè)整數(shù)m，代表敵方機(jī)器能使用的次數(shù)。

接下來m行，每行一個(gè)整數(shù)k_i，代表第i次后，有k_i個(gè)島嶼資源豐富，接下來k個(gè)整數(shù)h₁,h₂,…h(huán)_k，表示資源豐富島嶼的編號(hào)。

?

Output

輸出有m行，分別代表每次任務(wù)的最小代價(jià)。

?

?

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

?

?對(duì)于100%的數(shù)據(jù)，2<=n<=250000,m>=1,sigma(ki)<=500000,1<=ki<=n-1

?

Source

Stage2 day2

題解：

先發(fā)泄一下：

bzoj輸出量大了不能用cout!!!!!!!

bzoj輸出量大了不能用cout!!!!!!!

bzoj輸出量大了不能用cout!!!!!!!

艸艸艸艸艸艸卡了我一個(gè)下午!!!!!

接下說下關(guān)于虛樹的知識(shí)：

然后這道題就是虛樹+簡(jiǎn)單的樹形dp即可，注意在新建虛樹邊的時(shí)候不要直接memset，否則會(huì)超時(shí)····

代碼：

#include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> #include<ctime> #include<cctype> #include<string> #include<cstring> #include<algorithm> using namespace std; const int N=250005; int dfn[N],first[N],go[N*2],nxt[N*2],tot=0,n,m,g[N][26],deep[N],cnt=0,vn,tn,tem; int tot1=0,first1[N],go1[N*2],next1[N*2],par[N],tag[N]; int vir[N],stack[N],top=0; long long dp[N],val[N*2],minn[N]; inline void comb(int a,int b,long long c) {nxt[++tot]=first[a],first[a]=tot,go[tot]=b,val[tot]=c;nxt[++tot]=first[b],first[b]=tot,go[tot]=a,val[tot]=c; } inline void comb1(int a,int b) {next1[++tot1]=first1[a],first1[a]=tot1,go1[tot1]=b; } inline int R() {char c;int f=0;for(c=getchar();c<'0'||c>'9';c=getchar());for(;c<='9'&&c>='0';c=getchar())f=(f<<3)+(f<<1)+c-'0';return f; } inline long long Rl() {char c;long long f=0;for(c=getchar();c<'0'||c>'9';c=getchar());for(;c<='9'&&c>='0';c=getchar())f=f*10+c-'0';return f; } inline void dfs(int u,int fa) {dfn[u]=++cnt;for(int e=first[u];e;e=nxt[e]){int v=go[e];if(v==fa) continue;deep[v]=deep[u]+1;g[v][0]=u;minn[v]=min(minn[u],val[e]);dfs(v,u);} } inline int get(int a,int b) {int i,j;if(deep[a]<deep[b]) swap(a,b);for(i=0;(1<<i)<=deep[a];i++);i--;for(j=i;j>=0;j--){if(deep[a]-(1<<j)>=deep[b])a=g[a][j];}if(a==b) return a;for(j=25;j>=0;j--){if(g[a][j]!=g[b][j]){a=g[a][j];b=g[b][j];}}return g[a][0]; } inline void pre() {tot1=0,stack[top=0]=0,tem++; } bool cmp(const int &a,const int &b) {return dfn[a]<dfn[b]; } inline void build() {sort(vir+1,vir+vn+1,cmp);vn=unique(vir+1,vir+vn+1)-vir-1;tn=vn;for(int i=1;i<=tn;i++){int u=vir[i];if(!top){par[u]=0;stack[++top]=u;continue;}int lca=get(stack[top],u);while(deep[stack[top]]>deep[lca]){if(deep[stack[top-1]]<deep[lca]) par[stack[top]]=lca;top--;}if(stack[top]!=lca){vir[++vn]=lca;par[lca]=stack[top];stack[++top]=lca;}par[u]=lca;stack[++top]=u;}sort(vir+1,vir+vn+1,cmp); } inline long long solve(int u) {if(tag[u]==tem)return minn[u];dp[u]=minn[u];long long temp=0;bool flag=false;for(int e=first1[u];e;e=next1[e]){int v=go1[e];flag=true;temp+=solve(v);}if(flag) dp[u]=min(dp[u],temp);return dp[u]; } int main() {//freopen("a.in","r",stdin);n=R(); int a,b;long long c;for(int i=1;i<n;i++){a=R(),b=R(),c=Rl();comb(a,b,c);}minn[1]=1e+18;deep[1]=1;dfs(1,0);for(int i=1;i<=25;i++)for(int j=1;j<=n;j++)g[j][i]=g[g[j][i-1]][i-1];m=R();for(int i=1;i<=m;i++){pre(),vn=R();for(int j=1;j<=vn;j++)vir[j]=R(),tag[vir[j]]=tem;build();for(int j=1;j<=vn;j++)first1[vir[j]]=dp[vir[j]]=0;for(int j=2;j<=vn;j++)comb1(par[vir[j]],vir[j]);dp[vir[1]]=solve(vir[1]);printf("%lld\n",dp[vir[1]]);}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/AseanA/p/7485646.html

總結(jié)

以上是生活随笔為你收集整理的算法复习——虚树（消耗战bzoj2286）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。