哪里错了

P3366 【模板】最小生成树

emo_zkt @ 2024-02-20 14:19:19

各位帮一下忙,我就对了三个点,orz,谢谢

#include<bits/stdc++.h>
using namespace std;
const int maxn=5010;
int a[maxn][maxn],d[maxn],n,m,vis[maxn];
long long ans;
void prim(){
    memset(d,0x3f,sizeof d);
    d[1]=0;
    for(int k=1;k<=n;k++){
        int t=n+1;
        for(int i=1;i<=n;i++)
            if(vis[i]==0&&d[i]<d[t])t=i;
        vis[t]=1;
        for(int i=1;i<=n;i++){
            if(vis[i]==0&&d[i]>a[t][i])d[i]=a[t][i];
        }
    }
}
int main(){
    memset(a,0x3f,sizeof a);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int x,y,w;
        scanf("%d%d%d",&x,&y,&w);
        a[x][y]=a[y][x]=w;
    }
    prim();
    for(int i=1;i<=n;i++){
        if(d[i]==0x3f3f3f3f){
            ans=-1;
            break;
        }
        ans+=d[i];
    }
    if(ans==-1)cout<<"orz";
    else cout<<ans;
} 

by smll_wlm @ 2024-02-20 16:30:47

应该是最后

for(int i=1;i<=n;i++){
        if(d[i]==0x3f3f3f3f){
    ans=-1;
        break;
    }
    ans+=d[i];
}

不应该在这里用这种方式计算最小生成树的大小。因为n个点中,若有最小生成树则一定有且仅有n-1条边。那么对于 i:1->n的循环,除非那一条没连上的边恰好在最后,则一定进入if,使得ans=-1.

综上,正确的办法应该是在 prim 算法函数中进行计算与判断


by emo_zkt @ 2024-02-20 20:43:48

@smll_wlm 谢谢


|