P3959 [NOIP2017 提高組] 寶藏

題意:

額題意不好說，就是n個(gè)點(diǎn)m個(gè)邊，選定一個(gè)點(diǎn)為根節(jié)點(diǎn)，構(gòu)造一個(gè)最小生成樹，邊的權(quán)值為該該邊起點(diǎn)到根節(jié)點(diǎn)之間的點(diǎn)的數(shù)量K（不含根節(jié)點(diǎn)） * 道路長度
1<=n<=12
0<=m<=1e3
v<=5e5

題解:

參考題解
這數(shù)據(jù)范圍？暴力暴力暴力
不，我們用狀壓dp來做
我們設(shè)dp[i][j]表示用到第i個(gè)元素，當(dāng)前連接狀態(tài)為j的花費(fèi)的最小值
這個(gè)式子沒辦法直接轉(zhuǎn)移，因?yàn)槊總€(gè)邊的花費(fèi)是不一樣的，即k是不一樣的，我們可以重新設(shè)計(jì)一個(gè)狀態(tài)，我們將k值理解為距離初始化點(diǎn)的層數(shù)，如圖

被涂藍(lán)色的就是根節(jié)點(diǎn)，k就是劃分的層數(shù)
這樣我們設(shè)dp[i][j]表示到第i層，總共取了的點(diǎn)的狀態(tài)為j
轉(zhuǎn)移為：
dp[i][j] = min(dp[i-1][k]+trans[k][j] * (i-1))
trans[k][j] * (i-1)就是題目說的距離 * K(題目中說的k)
k是j的子集，即有可能轉(zhuǎn)移到j(luò)的狀態(tài)
trans[k][j]表示從狀態(tài)k轉(zhuǎn)移到狀態(tài)j的最小花費(fèi)路徑
這個(gè)子集意思就是：sub就是S的子集
這個(gè)子集怎么求？？
直接求2^n必然不行，會(huì)T，有小技巧
由公式：

for (int sub = S; sub; sub = (sub - 1) & S) {// sub 為 S 的子集 }

證明過程

最終答案就是：min(dp[i][2ⁿ-1])
初始化：dp[1][2^(i-1)] = 0 (i∈[1,n])
我感覺代碼很妙，思路也很妙，讓我想是真寫不出來
我詳細(xì)說trans如何求：
現(xiàn)在i是當(dāng)前狀態(tài)，j是i的子狀態(tài)，我們現(xiàn)在要狀態(tài)轉(zhuǎn)移從j–>i
temp=i ^ j,即要轉(zhuǎn)移的點(diǎn)(因?yàn)?^ 為不同為1)
然后我們開始枚舉temp中存在的點(diǎn)k(從高位往低位)，然后求從k到j(luò)的最短距離tmin，把tmin加入到trans[j][i]中

代碼：

#include<iostream> #include<cstdio> #include<cstring> using namespace std; long long read() {long long x=0,f=1; char c=getchar();while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();}return x*f; } const int N=12+2; const int M=1<<N; int n,m,dis[N][N],trans[M][M],POW[N]; long long f[N][M]; int main() {n=read(),m=read();memset(dis,0x3f,sizeof dis);for(int i=1;i<=m;i++){int s=read(),t=read(),v=read();if(dis[s][t]>v)dis[s][t]=dis[t][s]=v;}for(int i=0;i<(1<<n);i++)for(int j=i;j!=0;j=(j-1)&i){bool OK=true;int temp=i^j;//狀態(tài)i與狀態(tài)j的不同之處，狀態(tài)轉(zhuǎn)移為j->i for(int k=n-1;k>=0;k--){if((temp>>k)&1)//說明點(diǎn)k是轉(zhuǎn)移中增加的點(diǎn)，即 j沒有，i有 {int tmin=0x3f3f3f3f;for(int L=1;L<=n;L++)if(1&(j>>(L-1)))//如果狀態(tài)j包含此點(diǎn) ,求出L到k+1的最短距離//if(((1<<(L-1))&j)==(1<<(L-1))) tmin=min(tmin,dis[L][k+1]);if(tmin==0x3f3f3f3f)//如果此路無法走通 {OK=false;break;}trans[j][i]+=tmin;/*相當(dāng)于把j到i這段路拆分成了好幾份 */ temp-=(1<<k);}}if(OK==false)trans[j][i]=0x3f3f3f3f;}memset(f,0x3f,sizeof f);for(int i=1;i<=n;i++)f[1][(1<<(i-1))]=0;for(int i=2;i<=n;i++)for(int j=0;j<(1<<n);j++)for(int k=j;k!=0;k=(k-1)&j)//k為j的子狀態(tài)，也就是k是j的子集 if(trans[k][j]!=0x3f3f3f3f)//說明可以從狀態(tài)k到j(luò) f[i][j]=min(f[i][j],f[i-1][k]+(i-1)*trans[k][j]);long long ans=0x3f3f3f3f3f3f3f3fll;for(int i=1;i<=n;i++)ans=min(ans,f[i][(1<<n)-1]);printf("%lld",ans);return 0; }

總結(jié)

以上是生活随笔為你收集整理的P3959 [NOIP2017 提高组] 宝藏的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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