oval_m @ 2022-01-25 17:16:39
看着书上码的
#include <iostream>
#include <cstring>
#include <algorithm>
#define ll unsigned long long
using namespace std;
int va[5005], vb[5005];
ll w[200005];
int r[200005]; //排序后的w序号 边的
int p[5005]; //并查集 点的
int vexnum, arcnum;
bool cmp(const int a, const int b) { return w[a] < w[b]; }
int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); } //在查找的同时更新p数组
int main()
{
ios::sync_with_stdio(false);
cin >> vexnum >> arcnum;
memset(w, -1, sizeof(w)); //w初始化为ULLONG_MAX 18446744073709551615
int a, b;
ll ww;
for (int i = 0; i < arcnum; i++) //直接读入
{
cin >> va[i] >> vb[i] >> w[i];
}
for (int i = 0; i < vexnum; i++)
p[i] = i; //p[x]为节点x的父节点 没有父节点p[x]=x
for (int i = 0; i < arcnum; i++)
r[i] = i;
sort(r, r + arcnum, cmp); //将权值小的边排前面 采用间接排序
ll ans = 0;
for (int i = 0; i < arcnum; i++)
{
int x, y;
int temp = r[i];
x = find(va[temp]);
y = find(vb[temp]);
if (x != y)
{
p[x] = y;
ans += w[temp];
}
}
cout << ans;
}
by Cerisier @ 2022-01-25 20:41:32
我的问题 /dk
by 「 」 @ 2022-01-26 20:52:20
@oval_m 所以我说,你数组开小了,你为什么不信啊。
by oval_m @ 2022-01-29 01:56:07
@「 」 果然! 感谢