prim
Description
Input
Output
Sample Input
4 0 4 9 21 4 0 8 17 9 8 0 16 21 17 16 0
Sample Output
28
#include<stdio.h> int main(){ int tre[102][102]; int n; while(~scanf("%d",&n)){ for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){ scanf("%d",&tre[i][j]); } int min[102]={0}; int sum=0;int cmp;int mi=1000000; min[1]=1;//1表示点被连进来了 int minsum[102]; for(int r=1;r<=n;r++){ minsum[r]=tre[1][r]; } for(int k=1;k<=n-1;k++) { mi=1000000; for(int t=1;t<=n;t++){ if(min[t]!=1&&minsum[t]>0&&minsum[t]<mi){ cmp=t; mi=minsum[t];//得到min } } sum+=mi; min[cmp]=1;//该点被连接 //进行更新 for(int yy=1;yy<=n;yy++) { if(min[yy]==1){ for(int hh=1;hh<=n;hh++){ if(min[hh]!=1){ if(tre[yy][hh]<minsum[hh]) minsum[hh]=tre[yy][hh]; } } } } } printf("%d\n",sum); } return 0; }
版权声明:本文为博主原创文章,未经博主允许不得转载。
优质内容筛选与推荐>>长按二维码向我转账
受苹果公司新规定影响,微信 iOS 版的赞赏功能被关闭,可通过二维码转账支持公众号。
已发送
发送中
微信扫一扫
关注该公众号