prim+优先队列，最后一个点t掉了，求调

julihui325 @ 2024-08-01 16:45:26

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
inline int read(){
    int x=0;
    short f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}  

struct edge{
    int to,nxt,w;
}e[400010];
struct node{
    int id,dist;
    bool operator < (node x) const{
        return x.dist<dist;
    }
};
int head[200010],tot;
void add(int u,int v,int w){
    e[++tot].to=v;
    e[tot].nxt=head[u];
    e[tot].w=w;
    head[u]=tot;
}
int n,m,dis[5010];
bool vis[5010];
priority_queue <node> q;
int main(){
    int u,v,w,cnt=0,ans=0;
    n=read(),m=read();
    for(int i=1;i<=m;i++){
        u=read();
        v=read();
        w=read();
        add(u,v,w);
        add(v,u,w);
    }
    for(int i=1;i<=n;i++)
        dis[i]=0x3f3f3f3f;
    q.push((node){1,0});
    while(!q.empty()||cnt<n-1){
        node t=q.top();
        q.pop();
        u=t.id;
        if(vis[u])
            continue;
        vis[u]=1;
        ans+=t.dist;
        cnt++;
        for(v=head[u];v;v=e[v].nxt){
            if(e[v].w<dis[e[v].to]){
                dis[e[v].to]=e[v].w;
                q.push((node){e[v].to,e[v].w});             
            }
        }
    }
    if(cnt<n-1)
        printf("orz");
    else
        cout<<ans;
    return 0;
}

by jimmy0926 @ 2024-08-01 16:54:08

@julihui325 最后一个点是 orz。

by jimmy0926 @ 2024-08-01 16:55:42

图不一定是连通图 + priority_queue 常数不小

by jimmy0926 @ 2024-08-01 16:56:53

我不太看得懂你的代码

by jimmy0926 @ 2024-08-01 16:57:49

加点注释吧。

我喜欢用 Kruskal。

by qazsedcrfvgyhnujijn @ 2024-08-01 17:00:32

先判图是否连通
好像 kruskal 在不连通图会输出错误结果，而 prim 会 TLE

by jimmy0926 @ 2024-08-01 17:01:01

&您的 dis_1 用的 0x3f3f3f3f，不知道有没有影响

by jimmy0926 @ 2024-08-01 17:02:08

球关

验证码 ak9f 祭

by jimmy0926 @ 2024-08-01 17:08:00

您也可以改用 Kruskal。给一份板子呆码

#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 julihui325 @ 2024-08-01 17:19:18

@jimmy0926 笑点解析：kruskal刚调完，20分钟，prim两小时hhh&已关

by julihui325 @ 2024-08-01 17:19:55

@qazsedcrfvgyhnujijn 谢谢大佬，已关