題目背景
三大戰役的平津戰場上，傅作義集團在以北平、天津為中心，東起唐山西至張家口的鐵路線上擺起了一字長蛇陣，并企圖在潰敗時從海上南逃或向西逃竄。為了就地殲敵不讓其逃走，指揮官制定了先切斷敵人東西兩頭退路然后再逐個殲滅敵人的戰略方針。秉承偉大軍事家的戰略思想，作為一個有智慧的軍長你，遇到了一個類似的戰場局面。
題目描述
現在有?N?個城市，其中?K?個被敵方軍團占領了，N?個城市間有?N?1?條公路相連，破壞其中某條公路的代價是已知的，現在，告訴你?K?個敵方軍團所在的城市，以及所有公路破壞的代價，請你算出花費最少的代價將這?K?個地方軍團互相隔離開，以便第二步逐個擊破敵人。
輸入格式
第一行包含兩個正整數?N?和?K。
第二行包含?K?個整數，表示哪個城市被敵軍占領。
接下來?N?1?行，每行包含三個正整數?a,b,c，表示從?a?城市到?b?城市有一條公路，以及破壞的代價?c。城市的編號從?0?開始。
輸出格式
輸出一行一個整數，表示最少花費的代價。
輸入輸出樣例
輸入 #1復制
5 3 1 2 4 1 0 4 1 3 8 2 1 1 2 4 3
輸出 #1復制
4
說明/提示
對于?10%?的數據，N≤10。
對于?100%?的數據，2≤N≤105，2≤K≤N，1≤c≤106。
代碼實現：
#include<cstdio>
#include<algorithm>
#define MAX_NODE 100001
#define MAX_EDGE 200001
#define Loop(var, start, end) for(int var = start; var <= end; ++var)
using namespace std;
typedef long long LongLong;
// 圖的相關變量
int edgeCount; ? ? ? ? ? ? ? ?// 邊的數量計數器
int headNode[MAX_NODE]; ? ? ? // 每個節點的邊鏈表頭
int targetNode[MAX_EDGE]; ? ? // 邊指向的目標節點
int nextEdge[MAX_EDGE]; ? ? ? // 下一條邊的索引
int edgeWeight[MAX_EDGE]; ? ? // 邊的權重
// 添加邊的函數
inline void addEdge(int fromNode, int toNode, int weight) {
targetNode[++edgeCount] = toNode;
nextEdge[edgeCount] = headNode[fromNode];
headNode[fromNode] = edgeCount;
edgeWeight[edgeCount] = weight;
}
LongLong result; ? ? ? ? ? ? ?// 最終結果
bool isSpecialNode[MAX_NODE]; // 標記是否為特殊節點
// 深度優先搜索函數
// 返回值：子樹中能保留的最大最小邊權重
inline int dfs(int currentNode, int parentNode) {
LongLong totalSum = 0; ? ?// 子樹中所有有效邊的總和
LongLong maxEdge = 0; ? ? // 子樹中最大的有效邊
LongLong currentEdge; ? ? // 當前邊的權重（取最小值）
// 遍歷當前節點的所有邊
for(int edgeIndex = headNode[currentNode]; edgeIndex; edgeIndex = nextEdge[edgeIndex]) {
int neighborNode = targetNode[edgeIndex];
if(neighborNode == parentNode) continue;
// 遞歸計算子樹，取返回值和當前邊權重的最小值
currentEdge = min((LongLong)dfs(neighborNode, currentNode), (LongLong)edgeWeight[edgeIndex]);
totalSum += currentEdge;
maxEdge = max(maxEdge, currentEdge); ?// 更新最大邊
}
result += totalSum;
// 如果是特殊節點，返回一個很大的值表示這條路徑需要保留
if(isSpecialNode[currentNode]) return 1e9;
// 非特殊節點，減去最大邊并返回該值
result -= maxEdge;
return maxEdge;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("pro.in", "r", stdin);
freopen("pro.out", "w", stdout);
#endif
int nodeCount, specialCount;
scanf("%d%d", &nodeCount, &specialCount);
// 標記特殊節點
Loop(i, 1, specialCount) {
int node;
scanf("%d", &node);
isSpecialNode[node] = true;
}
// 讀取并添加所有邊
Loop(i, 1, nodeCount - 1) {
int u, v, weight;
scanf("%d%d%d", &u, &v, &weight);
addEdge(u, v, weight);
addEdge(v, u, weight);
}
// 從節點0開始深度優先搜索
dfs(0, -1);
// 輸出結果
printf("%lld", result);
return 0;
}
)
