PAT : 数据结构与算法题目集(中文)7-10 公路村村通
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
int UnionF[1001];
struct Heapstruct
{
int head, tail, value;
};
bool Compare(const Heapstruct &a, const Heapstruct &b)
{
return a.value > b.value;
}
int getdigit(void)
{
int temp{0};
while (1)
{
char ch = getchar();
if (ch == ' ' || ch == '\n' || ch == EOF)
return temp;
temp = temp * 10 + ch - '0';
}
}
int GetFind(const int num)
{
if (UnionF[num] <= -1)
return num;
UnionF[num] = GetFind(UnionF[num]);
return UnionF[num];
}
bool Find(const int &a, const int &b)
{
int qa = GetFind(a);
int qb = GetFind(b);
if (qa != qb)
{
if (UnionF[qa] < UnionF[qb])
UnionF[qb] = qa;
else if (UnionF[qb] > UnionF[qa])
UnionF[qa] = qb;
else
{
--UnionF[qb];
UnionF[qa] = qb;
}
return true;
}
return false;
}
int main(int argc, char *argv[])
{
int N{getdigit()}, M{getdigit()}, SumValue{0}, EdgeAcc{0};
fill(begin(UnionF), end(UnionF), -1);
vector<Heapstruct> T(M);
for (int i = 0; i < M; ++i)
{
T[i].head = getdigit();
T[i].tail = getdigit();
T[i].value = getdigit();
}
make_heap(T.begin(), T.end(), Compare);
while (EdgeAcc != N-1 && !T.empty())
{
Heapstruct temp{T[0]};
pop_heap(T.begin(), T.end(), Compare);
T.pop_back();
if (Find(temp.head, temp.tail))
{
SumValue += temp.value;
++EdgeAcc;
}
}
if (T.empty())
printf("-1\n");
else
printf("%d\n", SumValue);
return EXIT_SUCCESS;
}
考虑到题目中说边数最多为顶点数的三倍,采用 Kruskal 算法,并查集(路径压缩+按高度合并)维护连通性。