RainSpark @ 2022-06-25 14:21:03
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#define ull unsigned long long
#define ll long long
#define N 200005
#define INF 0x3f3f3f3f
using namespace std;
int head[N], num_edge;
int dis[N];
bool vis[N];
struct Edge {
int nxt, to, dis;
} edge[2 * N];
void add(int from, int to, int dis) {
num_edge++;
edge[num_edge].nxt = head[from];
edge[num_edge].to = to;
edge[num_edge].dis = dis;
head[from] = num_edge;
}
int cnt, n, m, tot, now = 1, ans;
int main() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
add(u, v, w); //双向加边
add(v, u, w);
}
for (int i = 2; i <= n; i++)
dis[i] = INF;
for (int i = head[1]; i; i = edge[i].nxt) {
dis[edge[i].to] = min(dis[edge[i].to], edge[i].dis);
}
for (int i = 1; i <= n; i++) {
if (tot >= n - 1)
break;
int minn = INF;
vis[now] = 1;
for (int j = 1; j <= n; j++) { //枚举每一个没有使用的点,找出最小值作为新边
if (vis[j] == 0 && minn > dis[j]) {
minn = dis[j];
now = j;
}
}
ans += minn;
for (int j = head[now]; j; j = edge[j].nxt) { //枚举now的所有连边,更新dist数组
int v = edge[j].to;
if (dis[v] > edge[j].dis && vis[v] == 0) {
dis[v] = edge[j].dis;
}
}
tot++;
}
if (tot == n - 1)
cout << ans << endl;
else
cout << "orz" << endl;
return 0;
}
by Revdream @ 2022-06-25 14:34:37
在这份代码里tot绝对等于n
by Revdream @ 2022-06-25 14:35:18
打错了,是n-1
by RainSpark @ 2022-06-25 14:38:41
@iyag 那Prim判断所有的点都加入的条件是什么?
by Revdream @ 2022-06-25 14:42:35
应该是在最后时枚举每个点(我只会克鲁斯卡尔)
by RainSpark @ 2022-06-25 14:43:22
@iyag 被P1265搞的
by metaphysis @ 2022-06-25 14:46:03
@takeoff37808
您的实现无法正确处理非连通图。Hack 数据:
3 1
1 2 1
by metaphysis @ 2022-06-25 14:57:53
加一句即可:
//...
if (minn == INF) break;
ans += minn;
//...
by Strelitzia_ @ 2022-06-25 15:29:36
可以在 while
里面两个 for
中间加一句:
if(vis[now]){
puts("orz");
return 0;
}
by RainSpark @ 2022-06-25 15:55:15
@metaphysis @yuzhihang016 @iyag AC了,万分感谢!