原题
点此链接1
题目分析
可参考课本(高等教育出版社 - 陈越 - 《数据结构》)P225中关于prim算法的描述解题。
本题相对于课本描述的算法来说,不需要考虑 父节点 (parent),只需要考虑一个总的WPL就行。
代码
#include <algorithm>
#include <iostream>
#include <map>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;
const int intMax = pow(2, 15) - 1;
int main()
{
int v, e;
cin >> v >> e;
vector<vector<pair<int, int>>> data(v);
for (auto i = 0; i < e; i++)
{
int p1, p2, cost;
cin >> p1 >> p2 >> cost;
data[p1 - 1].push_back({p2 - 1, cost});
data[p2 - 1].push_back({p1 - 1, cost});
}
vector<int> dis(v, intMax);
auto MinIndex = [&dis, v]() -> int {
auto index = -1;
auto min = intMax;
for (auto i = 0; i < v; i++)
if (dis[i] < min && dis[i])
{
index = i;
min = dis[i];
}
return index;
};
auto sum = 0;
dis[0] = 0;
for (auto &r : data[0])
dis[r.first] = r.second;
while (true)
{
auto minIndex = MinIndex();
if (minIndex == -1)
break;
sum += dis[minIndex];
dis[minIndex] = 0;
for (auto &r : data[minIndex])
if (dis[r.first] && dis[r.first] > r.second)
dis[r.first] = r.second;
}
if (count_if(dis.begin(), dis.end(), [](int in) { return !in; }) != v)
cout << -1 << endl;
else
cout << sum << endl;
return 0;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)