P3959 宝藏
P3959 寶藏
題目描述
參與考古挖掘的小明得到了一份藏寶圖,藏寶圖上標出了 nn 個深埋在地下的寶藏屋, 也給出了這 nn 個寶藏屋之間可供開發的 mm 條道路和它們的長度。
小明決心親自前往挖掘所有寶藏屋中的寶藏。但是,每個寶藏屋距離地面都很遠, 也就是說,從地面打通一條到某個寶藏屋的道路是很困難的,而開發寶藏屋之間的道路 則相對容易很多。
小明的決心感動了考古挖掘的贊助商,贊助商決定免費贊助他打通一條從地面到某 個寶藏屋的通道,通往哪個寶藏屋則由小明來決定。
在此基礎上,小明還需要考慮如何開鑿寶藏屋之間的道路。已經開鑿出的道路可以 任意通行不消耗代價。每開鑿出一條新道路,小明就會與考古隊一起挖掘出由該條道路 所能到達的寶藏屋的寶藏。另外,小明不想開發無用道路,即兩個已經被挖掘過的寶藏 屋之間的道路無需再開發。
新開發一條道路的代價是:
[mathrm{L} imes mathrm{K}
]
L代表這條道路的長度,K代表從贊助商幫你打通的寶藏屋到這條道路起點的寶藏屋所經過的 寶藏屋的數量(包括贊助商幫你打通的寶藏屋和這條道路起點的寶藏屋) 。
請你編寫程序為小明選定由贊助商打通的寶藏屋和之后開鑿的道路,使得工程總代 價最小,并輸出這個最小值。
錯誤日志: 錯太多次了。。寫總結寫下面好了
Solution
經由很多人討論得出, 此題靠譜正解為搜索
搜索啊, 毒瘤啊
那么現在談談這題怎么剪枝
首先最基本的最優化剪枝, 包含兩點:
最優化剪枝
當搜索到某處發現此時記錄的答案已經沒有記錄的最優答案優, 結束此次搜索
設計一個估價, 為當前狀態下, 至少需要多少代價才能到達目標狀態, 當估價值加上現值大于最優記錄答案, 結束此次搜索
啥意思呢? 就是你要設計一個東西, 記為 (g(x)), 且 (g(x) leq) 現實值
當如今 (tot + g(x) geq ans) 說明 現實值$ + tot < ans$ , 此時在搜索下去已經沒有意義了, 需要返回
設計的 (g(x)) 需要容易計算, 其值越接近現實值剪枝效率越高
因為此題中說明了小明建出來的東西是一顆樹, 所以每個點只會僅僅被一個點更新
故我們記錄到這個點 (x) 的最小距離, 記為 (MIN_{x}), 當前已決策集合為 (S)
那么估價函數就設為 $$sum_{i
otin S}MIN_{i}$$
其一定小于現實值沒得洗
每向決策中加入一個點, 就從估價里拿出這部分, 當把點去除時加回去即可
優化搜索順序
把 (dfs) 看做建一棟樓
那么搜索的過程就是不斷建樓, 拆樓的過程
建到最后發現建得不和自己的心意(邊界), 亦或是建到一半發現太丑了最后肯定看不得(剪枝)
你會把樓拆了繼續堅持建下去, 直到嘗試完所有可行的建法為止(搜索結束)
不斷嘗試 更新 進步 超越
這就是固執的 (dfs)
人生亦然啊
咳咳扯得有點遠
說真的老拆樓建樓挺累的
能不能設計一個藍圖
讓我們能盡可能少拆樓呢?
要拆也是盡量少拆, 然后在這個基礎上繼續建
這就是優化搜索順序
感性理解了以后, 我們在代碼基礎上認識一下如何在代碼中實現優化搜索順序
簡單來說, 我們需要確定一種搜索順序, 使得重復搜索的規模盡可能小
此題中, 我們先確定搜索框架: 枚舉已選中的點, 對于這些點選定還未加入集合的點, 加入并更新答案, 進一步加深搜索
那么怎么確定搜索順序使其最優呢?
通過觀察, 我們可以發現, 當確定選中的點后, 我們選未加入集合的點, 對于同一個點, 搜索完后只有兩個可能:
此點被選中, 此時選中集合改變
此點沒被選中, 那么這個點(在這個集合狀態下)不可能在被選了
綜上, 我們設立兩個起點, (begin1, begin2), 前一個記錄選中集合內點枚舉到了哪個, 后一個記錄在當前集合下枚舉沒入集合的點到了哪個
新一輪搜索時, 從斷點開始, 大大減少搜索量
Code
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#define LL long long
#define REP(i, x, y) for(int i = (x);i <= (y);i++)
using namespace std;
int RD(){
int out = 0,flag = 1;char c = getchar();
while(c < '0' || c >'9'){if(c == '-')flag = -1;c = getchar();}
while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();}
return flag * out;
}
const int maxn = (1 << 19), INF = 1e9;
int map[19][19];
int from[19];
int num, nr, leave;
int ans = INF;
bool in[19];
int cnt, lev[19];
int vis[19];
void dfs(int tot, int begin1, int begin2){
if(cnt == num){ans = min(ans, tot);return ;}
if(tot >= ans)return ;
REP(i, begin1, cnt){
int u = vis[i];
if(lev[u] * leave + tot >= ans)return ;
REP(v, begin2, num){
if(!in[v] && map[u][v] != INF){
vis[++cnt] = v;
in[v] = 1, lev[v] = lev[u] + 1;
leave -= map[from[v]][v];
dfs(tot + map[u][v] * lev[u], i, v + 1);
cnt--;
in[v] = 0, lev[v] = 0;
leave += map[from[v]][v];
}
}
begin2 = 1;
}
}
int main(){
num = RD(), nr = RD();
REP(i, 1, num)REP(j, 1, num)map[i][j] = INF;
REP(i, 1, nr){
int u = RD(), v = RD(), dis = RD();
map[u][v] = map[v][u] = min(map[u][v], dis);
}
REP(i, 1, num){
int minn = INF;
REP(j, 1, num){
if(map[j][i] < minn){
minn = map[j][i];
from[i] = j;//找一個最短的來自點作為最優預算
}
}
leave += minn;
}
REP(i, 1, num){
in[i - 1] = 0, lev[i - 1] = 0;
in[i] = 1, lev[i] = 1;
leave -= map[from[i]][i];
vis[cnt = 1] = i;
dfs(0, 1, 1);
leave += map[from[i]][i];
}
printf("%d
", ans);
return 0;
}
總結
- 上一篇: CXF 客服端调用报错
- 下一篇: NoticeBoard