「最小生成树」Prim

Links

Luogu P3366

Code

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=5000+5;
int ans=0;
int A,B;
int q[maxn][maxn],dis[maxn],book[maxn];
int main(){
    scanf("%d%d",&A,&B);
    for(int i=1;i<=B;i++){
    int x,y,z;
    scanf("%d%d%d",&x,&y,&z);
    if(!q[x][y])
        q[x][y]=q[y][x]=z;
        else
        q[x][y]=q[y][x]=min(q[x][y],z);
    }
    for(int i=1;i<=A;i++) dis[i]=0x7fffffff;//最小生成树初始化
    dis[1]=0; 
    for(int i=1;i<=A;i++){
        int mindt=0x7fffffff,k;
        for(int j=1;j<=A;j++)
            if(!book[j] && dis[j]<mindt){
                mindt=dis[j];
               	k=j;
            }
        if(mindt==0x7fffffff){//没有最小生成树(即图不连通)
            printf("orz\n"); 
            return 0;
        }
        ans+=mindt;//加上本次找到的最短安全边
        book[k]=1;
        for(int j=1;j<=A;j++)
            if(!book[j] && q[k][j] && q[k][j]<dis[j]) dis[j]=q[k][j];   
    }
    printf("%d\n",ans);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注