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 谢谢