Prim全部0分,大佬帮我康康哪里错了~

P3366 【模板】最小生成树

rc_Taurus @ 2023-02-03 14:42:18

#include<bits/stdc++.h>
#pragma GCC optmize(2)
using namespace std;
#define int long long
#define inf 2147483647
int n,m,edge[5005][5005],lowcost[5005],closest[5005],sum,cnt=1;
bool flag[5005];
void prim(int n){//n表示有n个节点
    flag[1]=true;
    for(int i=1;i<=n;i++){
        if(i==1)lowcost[i]=0;
        else{
            flag[i]=false;
            closest[i]=1;
            lowcost[i]=edge[1][i];
        }
    }
    //下面就有点类似Dijkstra的代码
    for(int i=1;i<n;i++){
        int temp=inf,t=-1;
        for(int j=1;j<=n;j++){
            if((!flag[j])&&lowcost[j]<temp){
                t=j;
                temp=lowcost[j];
            }
        }
        if(t==-1)break;
        flag[t]=true;
        sum+=temp; 
        cnt++;
        //更新
        for(int j=1;j<=n;j++){
            if((!flag[i])&&(lowcost[j]>edge[t][j])){
                lowcost[j]=edge[t][j];
                closest[j]=t;
            }
        }
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i==j)edge[i][j]=0;
            else edge[i][j]=inf;
        }
    }
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        edge[u][v]=edge[v][u]=w;
    }
    prim(n);
    if(cnt==n)cout<<sum;else cout<<"orz";
    return 0;
}

by rc_Taurus @ 2023-02-03 14:44:10

lowcost[j]表示集合U-V中点j到集合U的最短距离。

closet[j]表示集合U-V中点j到集合U的最邻近点


by __cheems__ @ 2023-03-14 15:52:10

prim算法应该还要再加个堆优化,不然会TLE。


|