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 _Goodnight @ 2022-01-25 17:20:39
@oval_m 不懂就问 memset置-1会变成什么样
by Cerisier @ 2022-01-25 17:22:47
@_Goodnight 数组中每个数都是 -1
by Cerisier @ 2022-01-25 17:23:22
应该是的，您可以自己本地试试 qwq
by 「 」 @ 2022-01-25 17:25:06
@oval_m 你边记录端点的数组开小了？
by mamingxiao @ 2022-01-25 17:26:14
这道题标号是从1开始的
by mamingxiao @ 2022-01-25 17:27:31
for (int i = 0; i < vexnum; i++)
p[i] = i; //p[x]为节点x的父节点 没有父节点p[x]=x改成
for (int i = 1; i <= vexnum; i++)
p[i] = i; //p[x]为节点x的父节点 没有父节点p[x]=x应该就可以了
by mamingxiao @ 2022-01-25 17:30:14
@Cerisier 这里memset应该会变成unsigned long long的最大值
by Cerisier @ 2022-01-25 17:42:55
@mamingxiao
不是吧？
#include<iostream>
#include<cstring>
using namespace std;
long long a[100010];
int main() {
memset(a, -1, sizeof(a));
cout << a[5] << endl;
return 0;
}这份代码输出 -1
by oval_m @ 2022-01-25 20:28:27
@Cerisier 我ll定义的是unsigned long long
by oval_m @ 2022-01-25 20:30:10
@mamingxiao 还是一样