Prim全部0分,大佬帮我康康哪里错了~
查看原帖
Prim全部0分,大佬帮我康康哪里错了~
922943
rc_Taurus楼主2023/2/3 14:42
#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;
}
2023/2/3 14:42
加载中...