求助,刚学Prim,最后一个特判点WA

P3366 【模板】最小生成树

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了,万分感谢!


|