首页 > 代码库 > XXy

XXy

XXy

codevs1003

技术分享

帮我看看

#include<iostream>#include<cstdio>using namespace std;int dis[200],map[200][200],n,num,cost,fa[200],point[200];bool vis[200];void Prim(int s,int t){    for(int i=1;i<=n;i++)dis[i]=0x7f;    dis[s]=0;int pre=1;    for(int i=1;i<=n;i++){        int Min=0x7f,k=0;        for(int j=1;j<=n;j++){            if((dis[j]<Min)&&(vis[j]==0))            Min=dis[j],k=j,point[num]=k;        }        if(Min==0x7f)break;        cost+=Min;        vis[k]=1;        for(int j=1;j<=n;j++){            if((map[k][j]<dis[j])&&(vis[j]==0))dis[j]=map[k][j],fa[j]=k;        }        if(Min!=0)num++;        pre=k;    }}int main(){    scanf("%d",&n);    for(int i=1;i<=n;i++)        for(int j=1;j<=n;j++)            cin>>map[i][j];    Prim(1,n);    cout<<num<<endl;    for(int i=0;i<num;i++)    if(fa[point[i]]<point[i])cout<<fa[point[i]]<< <<point[i]<<endl;    else cout<<point[i]<< <<fa[point[i]]<<endl;    cout<<cost;}

 技术分享

XXy