DiDi123 @ 2022-04-11 22:32:42
事实证明,Prim中
下面的程序好像也能过
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100001
struct edge {
int to, w, nex;
} Edge[MAXN << 2];
int head[5005], tot, sum, cnt, vis[5005], n, m;
void add(int u, int v, int w) {
Edge[cnt].nex = head[u];
Edge[cnt].to = v;
Edge[cnt].w = w;
head[u] = cnt++;
}
struct node {
int pos, dis;
bool operator < (const node &x) const {
return dis > x.dis;
}
};
priority_queue <node> q;
void prim() {
node temp;
temp.dis = 0, temp.pos = 1;
q.push(temp);
while (!q.empty() && tot < n) {
int u = q.top().pos, w = q.top().dis;
q.pop();
if (vis[u]) continue;
tot++, sum += w;
vis[u] = 1;
for (int i = head[u]; i != -1; i = Edge[i].nex) {
temp.dis = Edge[i].w, temp.pos = Edge[i].to;
q.push(temp);
}
}
}
int main() {
memset(head, -1, sizeof(head));
int a1, a2, a3;
cin >> n >> m;
for (int i = 1; i <= m; i++) {
cin >> a1 >> a2 >> a3;
add(a1, a2, a3);
add(a2, a1, a3);
}
prim();
if (tot == n) cout << sum;
else cout << "orz";
}
by 蕾姆莉雅 @ 2022-04-13 22:53:54
%%%困扰了我好久的dis数组orz
by L1ngYu @ 2022-04-29 23:14:42
枚举下一个要走的点然后统计权值和就行。不需要更新