『寶藏 狀態壓縮DP NOIP2017』
寶藏(NOIP2017)
Description
參與考古挖掘的小明得到了一份藏寶圖,藏寶圖上標出了 n 個深埋在地下的寶藏屋, 也給出了這 n 個寶藏屋之間可供開發的m 條道路和它們的長度。
小明決心親自前往挖掘所有寶藏屋中的寶藏。但是,每個寶藏屋距離地面都很遠, 也就是說,從地面打通一條到某個寶藏屋的道路是很困難的,而開發寶藏屋之間的道路 則相對容易很多。
小明的決心感動了考古挖掘的贊助商,贊助商決定免費贊助他打通一條從地面到某 個寶藏屋的通道,通往哪個寶藏屋則由小明來決定。
在此基礎上,小明還需要考慮如何開鑿寶藏屋之間的道路。已經開鑿出的道路可以 任意通行不消耗代價。每開鑿出一條新道路,小明就會與考古隊一起挖掘出由該條道路 所能到達的寶藏屋的寶藏。另外,小明不想開發無用道路,即兩個已經被挖掘過的寶藏 屋之間的道路無需再開發。
新開發一條道路的代價是:
\[L×K\]
L代表這條道路的長度,K代表從贊助商幫你打通的寶藏屋到這條道路起點的寶藏屋所經過的 寶藏屋的數量(包括贊助商幫你打通的寶藏屋和這條道路起點的寶藏屋) 。
請你編寫程式為小明選定由贊助商打通的寶藏屋和之後開鑿的道路,使得工程總代 價最小,並輸出這個最小值。
Input Format
第一行兩個用空格分離的正整數 n,m,代表寶藏屋的個數和道路數。
接下來 m 行,每行三個用空格分離的正整數,分別是由一條道路連線的兩個寶藏 屋的編號(編號為 1−n),和這條道路的長度 v。
Output Format
一個正整數,表示最小的總代價。
Sample Input
Sample Output
解析
簡單概括題意:給出一副無向圖,每條邊都有一個權值且均未開通,先可以隨便取一個起點,要開通一些邊,使它成為一個連通圖,開通一條邊的代價為這條邊的權值*起點到它的點的個數(起點也算),求最小代價。
資料範圍\(N<=12\) ,基本上可以確定是狀壓\(DP\) 了。我們直接最簡單地設定狀態:\(f[S]\) 代表以及取的節點的狀態為S的最小代價,那麼目標狀態就是\(f[(1<<n)-1]\) 。
如果考慮遞推求解的話,我們發現需要計算花費的深度會很難列舉,這就導致了
\(DP\)
順序的問題,如果選擇用記憶化搜尋求解的話,會方便很多。
由於起點不是確定的,我們需要用一重迴圈來列舉起點,然後以\(1<<(root-1)\) 為初始狀態,對每一種情況進行一次記憶化搜尋,記搜的大體思路如下:
1.對於狀態\(S\) ,列舉一個點\(i\) ,滿足\(i \in S\)
2.在列舉一個點\(j\) ,滿足\(i,j\) 有邊相連且\(j \notin S\)
3.狀態轉移方程:\(f[S']=min{f[S]+depth[i]*dis[i][j]}\)
4.更新新加入的節點j的深度
5.搜尋下一個狀態\(S'\)
6.回溯還原節點j的深度
最後在每一種情況的目標狀態中取個\(min\) 就是最終的答案了,時間複雜度\(O(n^32^n)\) 。
\(Code:\)
#include<bits/stdc++.h> using namespace std; const int N=15,M=10015,Smax=(1<<N)+20,INF=0x3f3f3f3f; int n,m,dis[N][N],f[Smax],depth[N],ans=INF; inline void input(void) { memset(dis,0x3f,sizeof dis); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { int u,v,val; scanf("%d%d%d",&u,&v,&val); dis[u][v]=dis[v][u]=min(dis[u][v],val); } } inline void Search(int S) { for(int i=1;i<=n;i++) { if((1<<(i-1))&S) { for(int j=1;j<=n;j++) { if(not ((1<<(j-1))&S)&&(dis[i][j]<INF)) { if(f[S|(1<<(j-1))]>f[S]+depth[i]*dis[i][j]) { int temp=depth[j]; depth[j]=depth[i]+1; f[S|(1<<(j-1))]=f[S]+depth[i]*dis[i][j]; Search(S|(1<<(j-1))); depth[j]=temp; } } } } } } inline void solve(void) { for(int root=1;root<=n;root++) { memset(f,0x3f,sizeof f); memset(depth,0x3f,sizeof depth); f[1<<(root-1)]=0; depth[root]=1; Search(1<<(root-1)); ans=min(ans,f[(1<<n)-1]); } } int main(void) { input(); solve(); printf("%d\n",ans); }