79分最小生成树求助,悬一关

P3366 【模板】最小生成树

ztyo_zysclown @ 2024-04-24 19:22:11

#include<bits/stdc++.h>
using namespace std;
const int N=520,INF=0x3f3f3f3f;
int n,m;
int g[N][N];
int dist[N];
bool st[N];
int prim(){
    memset(dist,0x3f,sizeof(dist));
    int res=0;
    for(int i=0;i<n;i++){
        int t=-1;
        for(int j=1;j<=n;j++){
            if(!st[j]&&(t==-1||dist[t]>dist[j])){
                t=j;
            }
        }//判断这个点对集合中的每一个点的边中最短的那一条 
        if(i&&dist[t]==INF) return INF;
        if(i) res+=dist[t];//点不能是一 
        for(int j=1;j<=n;j++){
            dist[j]=min(dist[j],g[t][j]);
        } //更新其他的点到集合的距离 
        st[t]=true;//入树 
    }
    return res;
}
int main(){
    cin>>n>>m;
    memset(g,0x3f,sizeof(g));
    while(m--){
        int u,v,m;
        cin>>u>>v>>m;
        g[u][v]=g[v][u]=min(g[u][v],m);
    }
//  for(int i=1;i<=n;i++){
//      cout<<dist[i]<<" ";
//  }
    int t=prim();
    if(t==INF){
        cout<<"orz";
        return 0;
    }
    cout<<t;
    return 0;
} 

by luuia @ 2024-04-24 19:34:09

N有5000不能用邻接表


by luuia @ 2024-04-24 19:35:15

改成链式前向星或者vector就对了


by elpsconr @ 2024-04-25 22:37:17

N改成5000就可以了,还有这个是邻接矩阵,不是邻接表,不要被楼上误导了.不过还是建议用链式前向星存图


|