Prim算法 #8 #9 #10 #13 WA,玄关
查看原帖
Prim算法 #8 #9 #10 #13 WA,玄关
1165197
Eastern_Leaf楼主2024/8/12 16:09
#include<bits/stdc++.h>
using namespace std;
int n,m;
struct edge{
    int fr,to,w;
} e[11451419];
int hd[11451419],nx[114514],tp = 0;
void build(int u,int v,int w){
    nx[tp+1] = hd[u];
    hd[u] = tp+1;
    e[tp +1].fr = u,e[tp+1].to = v,e[tp+1].w = w;
    tp++;
} 
int dis[114514],ans = 0,cur = 1,gs = 0;
bool vis[114514];
void prim(){
    memset(dis,0x3f,sizeof(dis));
    int minn=2e9;
    for(int i = hd[1];i>0;i = nx[i]){
        dis[e[i].to] = min(dis[e[i].to],e[i].w);
    }
    for(int i = 1;i<n;i++){
        vis[cur] = 1;
        for(int j = 1;j<=n;j++){
            if(dis[j] < minn&&vis[j] == 0){
                minn = dis[j];
                cur = j;
            }
        }
        ans += minn;
        gs++;
        for(int j = hd[cur];j>0; j= nx[j]){
            if(vis[e[j].to] == 0) {
                dis[e[j].to] = min(dis[e[j].to],e[j].w);
            }
        }
        minn = 2e9;
    }
}
int main(){
    memset(hd,0,sizeof(hd));
    memset(vis,0,sizeof(vis));
    cin>>n>>m;
    int u,v,w;
    for(int i = 1;i<=m;i++){
        cin>>u>>v>>w;
        build(u,v,w);
        build(v,u,w);
    }
    vis[1] = 1;
    prim();
    if(gs != n-1) {cout<<"orz";}
    else {cout<<ans;}
    return 0;
}
2024/8/12 16:09
加载中...