@[julihui325](/user/553577) 最后一个点是 orz。
by jimmy0926 @ 2024-08-01 16:54:08
图不一定是连通图 + priority_queue 常数不小
by jimmy0926 @ 2024-08-01 16:55:42
我不太看得懂你的代码
by jimmy0926 @ 2024-08-01 16:56:53
加点注释吧。
~~我喜欢用 Kruskal~~。
by jimmy0926 @ 2024-08-01 16:57:49
先判图是否连通
好像 kruskal 在不连通图会输出错误结果，而 prim 会 TLE
by qazsedcrfvgyhnujijn @ 2024-08-01 17:00:32
&您的 $dis_1$ 用的 $0x3f3f3f3f$，不知道有没有影响
by jimmy0926 @ 2024-08-01 17:01:01
~~球关~~
验证码 ak9f 祭
by jimmy0926 @ 2024-08-01 17:02:08
您也可以改用 Kruskal。给一份~~板子~~呆码
```cpp
#include <bits/stdc++.h>
#define made_by_jimmy0926 return 0
typedef long long ll;
int n, m, ptr;
ll ans;
int h[5001], f[5001];
struct Edge {
int start;
int to;
int val;
bool operator < (const Edge x) const {
return val < x.val;
}
} eg[200001];
void init() {
std::sort(eg + 1, eg + 1 + m);
for (int i = 1; i <= n; ++i) {
f[i] = i;
h[i] = 1;
}
}
int find(int x) {
if (f[x] == x)
return x;
return f[x] = find(f[x]);
}
inline void merge(int u, int v) {
u = find(u), v = find(v);
if (h[u] < h[v])
std::swap(u, v);
if (u != v) {
f[v] = u;
h[u] += (h[u] == h[v]);
}
}
bool isdiff(int u, int v) {
return find(u) != find(v);
}
inline bool judge() {
for (int i = 2; i <= n; ++i)
if (find(f[i]) != find(f[i - 1]))
return false;
return true;
}
bool kruskal() {
if (m < n - 1)
return false;
init();
int cnt = 0;
for (int i = 1; i <= m && cnt < n - 1; ++i)
if (isdiff(eg[i].start, eg[i].to)) {
// printf("choose : %d %d %d\n", eg[i].start, eg[i].to, eg[i].val);
++cnt;
ans += eg[i].val;
merge(eg[i].start, eg[i].to);
}
if (cnt < n - 1)
return false;
// printf("judging.\n");
return judge();
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; ++i) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
eg[++ptr] = {u, v, w};
}
bool ok = kruskal();
if (!ok)
printf("orz");
else
printf("%lld", ans);
made_by_jimmy0926;
}
```
较优解~~至少比一大群面向数据编程的【数据删除】要好~~
by jimmy0926 @ 2024-08-01 17:08:00
@[jimmy0926](/user/1162093)
笑点解析：kruskal刚调完，20分钟，prim两小时hhh&已关
by julihui325 @ 2024-08-01 17:19:18
@[qazsedcrfvgyhnujijn](/user/1198768)
谢谢大佬，已关
by julihui325 @ 2024-08-01 17:19:55