中文题目 7-50 畅通工程之局部最小花费问题 Prim和Kruskal
某地区经过对城镇交通状况的调查，得到现有城镇间快速道路的统计数据，并提出“畅通工程”的目标：使整个地区任何两个城镇间都可以实现快速交通（但不一定有直接的快速道路相连，只要互相间接通过快速路可达即可）。现得到城镇道路统计表，表中列出了任意两城镇间修建快速路的费用，以及该道路是否已经修通的状态。现请你编写程序，计算出全地区畅通需要的最低成本。
输入格式:
输入的第一行给出村庄数目 ()；随后的行对应村庄间道路的成本及修建状态：每行给出4个正整数，分别是两个村庄的编号（从1编号到），此两村庄间道路的成本，以及修建状态 — 1表示已建，0表示未建。
输出格式:
输出全省畅通需要的最低成本。
输入样例:
4
1 2 1 1
1 3 4 0
1 4 1 1
2 3 3 0
2 4 2 1
3 4 5 0
输出样例:
3思路:
最直接的还是Kruskal算法。根据题意，图中已经形成了一些“树林”，这刚好符合Kruskal算法的思路，可以将题目给出的情形看作是Kruskal算法处理了一半的结果。而Kruskal算法将已经收录的顶点视作一整棵树，根据未收录顶点到当前树的距离来排序，所以可以在输入时只记录未修建的路，直接用最小堆来适配。只要注意每收录一个顶点，MST预期的边数就减小1.
Prim算法也可以做，但感觉有些别扭，因为Prim算法是基于顶点来进行搜索的，每次想要更新dist数组都要基于一个特定的顶点，从而必须要在dist数组里区分开两个特殊语义：已修建status_biult和已收录status_collected，把它们分别用0和-1表示即可。不过Prim算法就不能在输入时忽略已修建好的路了，而是把修建好的路的预计花费（权值）修改为0；这样在算法中统一求和，循环到已经修好的路时，直接加0.
Kruskal算法
#include
#include
#include
using namespace std;
constexpr int kInfty = ~(1<<31), kMaxCityN = 100;
struct Road {
int from, to, expense;
bool operator<(const Road &r) const {
return expense > r.expense;
}
};
class UCSet {
public:
UCSet(int raw_list[], int cap):capacity{cap}, list{raw_list} {
for (int i = 0; i < capacity; ++i)
list[i] = -1;
}
bool unionSet(Road rd){
int x = find(rd.from),
y = find(rd.to);
if (x == y) return false;
else if (list[x] < list[y]){
list[x] += list[y];
list[y] = x;
}
else {
list[y] += list[x];
list[x] = y;
}
return true;
}
private:
int find(int x){
if (list[x] < 0) return x;
return list[x] = find(list[x]);
}
int capacity;
int *list;
};
int cityN, roadN;
priority_queue roads;
int ucset_raw[kMaxCityN];
int Kruskal(UCSet &MST, int eN_exp){
int wpl = 0;
int eN_Mst = 0;
while ( eN_Mst < eN_exp && !roads.empty() ){
Road crtR = roads.top(); //implement with minheap;
roads.pop();
if ( MST.unionSet(crtR) ){//if do not constitute circulation;
++eN_Mst;
wpl += crtR.expense;//roads is a minheap;
}
}
if (eN_Mst < eN_exp)
return -1;
return wpl;
}
void solution_Kruskal(){
scanf("%d ", &cityN);
UCSet MinSpanTree (ucset_raw, cityN);
roadN = cityN *( cityN - 1) / 2;
int expected_edgeN = cityN - 1;
for (int i = 0; i < roadN; ++i){
Road ri;
int isBiult;
scanf("%d %d %d %d ", &ri.from, &ri.to, &ri.expense, &isBiult);
if (isBiult == 0){
roads.push(ri);
}
else {//if not biult;
if ( MinSpanTree.unionSet(ri) )//if in one set, and union them;
--expected_edgeN;
}
}
printf("%d", Kruskal(MinSpanTree, expected_edgeN));
return;
}
int main(){
solution_Kruskal();
return 0;
} Prim算法
#include
#include
#include
using namespace std;
constexpr int kInfty = ~(1<<31), kMaxCityN = 100;
constexpr int stt_Collected = -1, stt_Biult = 0;
int cityN, roadN;
struct Elem {
int to, exps;
};
vector map[kMaxCityN];
int Prim(int vIdx){
//initilization;
int totExps = 0, vertCnt = 0;
int exps[kMaxCityN];
for (int i = 0; i <= cityN; ++i)
exps[i] = kInfty;
for (Elem e : map[vIdx])
exps[e.to] = e.exps;
/*Attention: differentiate status "collected" and "biult";*/
exps[vIdx] = stt_Collected;
++vertCnt;
while ( true ){
int crt = -1, minCost = kInfty;
for (int i = 1; i <= cityN; ++i)
if (exps[i] != stt_Collected && minCost > exps[i]){
crt = i;
minCost = exps[i];
}
if (crt == -1 ) break;
totExps += minCost;
exps[crt] = stt_Collected;//collect it;
++vertCnt;
for (Elem el : map[crt]){
if (exps[el.to] != stt_Collected){//if uncollected;
if (el.exps < exps[el.to])
exps[el.to] = el.exps;
}
}
}
if (vertCnt != cityN)
return -1;
return totExps;
}
void solution_Prim(){
scanf("%d ", &cityN);
roadN = cityN *( cityN - 1) / 2;
for (int i = 0;i < roadN; ++i){
int v1, v2, isBiult;
Elem ei;
scanf("%d %d %d %d ", &v1, &v2, &ei.exps, &isBiult);
if (isBiult)
ei.exps = stt_Biult;//here initiate expense to stt_Biult,
//which should be differentiated with stt_Collected;
ei.to = v2;
map[v1].push_back(ei);
ei.to = v1;
map[v2].push_back(ei);
}
int res = Prim(1);
printf("%d", res);
return;
}
int main(){
solution_Prim();
return 0;
}