@[Running_a_way](/user/693428) 可能是你数组开大了，你 $g$ 数组完全可以用一个函数来代替的
by _zzzzzzy_ @ 2023-08-19 19:35:17
@[zhangzhengyan0831](/user/715244) 啊？怎么写
by Running_a_way @ 2023-08-19 19:42:23
@[Running_a_way](/user/693428) 你不是完全图吗，你邻接矩阵写了跟没写一样，因为你的边的权值可以 $O(1)$ 算出来
by _zzzzzzy_ @ 2023-08-19 19:43:44
@[Running_a_way](/user/693428) 大概是这样
```cpp
//邻接矩阵
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
int n;
const int N = 5010;
double x[N], y[N];
// double g[N][N];
double dis[N]; int vis[N];
double g(int i, int j) {
return sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
}
double prim() {
for (int i = 1; i <= n; i++) dis[i] = 1e9;
double res = 0;
for (int i = 1; i <= n; i++) {
double mint = 1e9; int minid = -1;
for (int j = 1; j <= n; j++) {
if((minid == -1 || mint > dis[j]) && vis[j] == 0) {
mint = dis[j];
minid = j;
}
}
if(i != 1 && dis[minid] == 1e9) return -1;
if(i != 1) res += mint;
vis[minid] = 1;
for (int j = 1; j <= n; j++) {
dis[j] = min(dis[j], g(minid,j));
}
}
return res;
}
int main() {
ios::sync_with_stdio(false);
cin >> n;
for (int i = 1; i <= n; i++) cin >> x[i] >> y[i];
// for (int i = 1; i <= n; i++) {
// for (int j = 1; j <= n; j++) {
// if(i != j) {
// g[i][j] = sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
// }
// }
// }
printf("%.2lf\n", prim());
return 0;
}
```
by _zzzzzzy_ @ 2023-08-19 19:44:17
好的谢谢
by Running_a_way @ 2023-08-19 19:44:21
@[zhangzhengyan0831](/user/715244) 已 A，感谢。
此贴终。
by Running_a_way @ 2023-08-19 19:58:12