寶藏
- 題面
-
- Description
- Input
- Output
- Sample Input
-
- 【輸入樣例 1】
- 【樣例輸入 2】
- Sample Output
-
- 【輸出樣例 1】
-
- 【輸入輸出樣例 1 說明】
- 【樣例輸出 2】
-
- 【輸入輸出樣例 2 說明】
- Data Constraint
- 思路
- Code
-
- 後記
題面
Description
參與考古挖掘的小明得到了一份藏寶圖，藏寶圖上标出了 n 個深埋在地下的寶藏屋，也給出了這 n 個寶藏屋之間可供開發的 m 條道路和它們的長度。
小明決心親自前往挖掘所有寶藏屋中的寶藏。但是，每個寶藏屋距離地面都很遠，也就是說，從地面打通一條到某個寶藏屋的道路是很困難的，而開發寶藏屋之間的道路則相對容易很多。
小明的決心感動了考古挖掘的贊助商，贊助商決定免費贊助他打通一條從地面到某個寶藏屋的通道，通往哪個寶藏屋則由小明來決定。
在此基礎上，小明還需要考慮如何開鑿寶藏屋之間的道路。已經開鑿出的道路可以任意通行不消耗代價。每開鑿出一條新道路，小明就會與考古隊一起挖掘出由該條道路所能到達的寶藏屋的寶藏。另外，小明不想開發無用道路，即兩個已經被挖掘過的寶藏屋之間的道路無需再開發。
新開發一條道路的代價是：
這條道路的長度 × 從贊助商幫你打通的寶藏屋到這條道路起點的寶藏屋所經過的寶藏屋的數量（包括贊助商幫你打通的寶藏屋和這條道路起點的寶藏屋）。
請你編寫程式為小明標明由贊助商打通的寶藏屋和之後開鑿的道路，使得工程總代價最小，并輸出這個最小值。
Input
第一行兩個用空格分離的正整數 n 和 m，代表寶藏屋的個數和道路數。
接下來 m 行，每行三個用空格分離的正整數，分别是由一條道路連接配接的兩個寶藏屋的編号（編号為 1~n），和這條道路的長度 v。
Output
輸出共一行，一個正整數，表示最小的總代價。
Sample Input
【輸入樣例 1】
4 5
1 2 1
1 3 3
1 4 1
2 3 4
3 4 1
【樣例輸入 2】
4 5
1 2 1
1 3 3
1 4 1
2 3 4
3 4 2
Sample Output
【輸出樣例 1】
4
【輸入輸出樣例 1 說明】
小明標明讓贊助商打通了 1 号寶藏屋。小明開發了道路 1->2，挖掘了 2 号寶藏。開發了道路 1->4，挖掘了 4 号寶藏。還開發了道路 4->3，挖掘了 3 号寶藏。工程總代價為：1 × 1 + 1 × 1 + 1 × 2 = 4
(1->2) (1->4) (4->3)
【樣例輸出 2】
5
【輸入輸出樣例 2 說明】
小明標明讓贊助商打通了 1 号寶藏屋。小明開發了道路 1->2，挖掘了 2 号寶藏。開發了道路 1->3，挖掘了 3 号寶藏。還開發了道路 1->4，挖掘了 4 号寶藏。工程總代價為：1 × 1 + 3 × 1 + 1 × 1 = 5
(1->2) (1->3) (1->4)
Data Constraint
對于 20%的資料：
保證輸入是一棵樹，1≤n≤8，v≤5000 且所有的 v 都相等。
對于 40%的資料：
1≤n≤8，0≤m≤1000，v≤5000 且所有的 v 都相等。
對于 70%的資料：
1≤n≤8，0≤m≤1000，v≤ 5000
對于 100%的資料：
1≤n≤12，0≤m≤1000，v≤ 500000
思路
這題據我所知有三種方法：
1、随機化貪心
2、狀壓 D P DP DP
3、記憶化搜尋
第一種方法有資料能hack掉，第二種方法如果非正确 D P DP DP也會被hack。好像隻有 D F S DFS DFS不會被hack。（資料在後文，大家可以自己測試一下）。
我們設 f s , i , j f_{s,i,j} fs,i,j 表示擴充i節點，深度為j，狀态為s。
設 c i c_i ci表示第i個被擴充的節點。
設 b z i bz_i bzi表示第i個節點有沒有被擴充。
設 d e p i dep_i depi表示第i個節點的深度。
每次在c數組中選一個擴充過的節點擴充未擴充的節點，每次更新f數組即可。
Code
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
using namespace std;
int n,m,f[4500][105][105],e[105][105],ans=99999999,bz[105];
int dep[105],c[105];
int cheng[15]={0,1,2,4,8,16,32,64,128,256,512,1024,2048};
int dfs(int st,int now,int s,int res)
{
if(!res) return ans=min(ans,s);
if(f[st][now][dep[now]]<=s) return f[st][now][dep[now]];
if(ans<=s) return ans;
for(int i=1;i<=n;i++)
if(!bz[i])
{
bz[i]=1;
for(int j=1;j<=n-res+1;j++)
if(e[i][c[j]]>0)
{
dep[i]=dep[c[j]]+1;
c[n-res+1]=i;
f[st+cheng[i]*bz[i]][i][dep[i]]=min(f[st+cheng[i]*bz[i]][i][dep[i]],dfs(st+cheng[i]*bz[i],i,s+dep[c[j]]*e[i][c[j]],res-1));
dep[i]=0;
c[n-res+1]=0;
}
bz[i]=0;
}
return s;
}
int main()
{
freopen("treasure.in","r",stdin);
freopen("treasure.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int u,v,dis;
scanf("%d%d%d",&u,&v,&dis);
if(e[u][v]) e[u][v]=e[v][u]=min(e[u][v],dis);
else e[u][v]=e[v][u]=dis;
}
memset(f,0x3f,sizeof(f));
for(int i=1;i<=n;i++)
{
memset(bz,0,sizeof(bz));
memset(dep,0,sizeof(dep));
memset(c,0,sizeof(c));
bz[i]=1,dep[i]=1,c[1]=i;
dfs(bz[i]*cheng[i],i,0,n-1);
}
printf("%d",ans);
}
後記
前面我們說到的hack資料現在就給出：
hack1
hack2
hack3