POJ 1258 Agri-Net

浏览数：36 / 时间：2015年06月09日

最小生成树prim

 

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 #include <algorithm>
 5 #include <cmath>
 6 using namespace std;
 7 
 8 const int INF = 99999999 ;
 9 const int maxn = 105 ;
10 
11 int map[maxn][maxn];
12 int visit[maxn];
13 int low[maxn];
14 
15 int main (){
16     int n;
17     while (~scanf ("%d",&n)){
18         for (int i=1;i<=n;i++){
19             for (int j=1;j<=n;j++){
20                 scanf ("%d",&map[i][j]);
21             }
22             map[i][i]=INF;
23         }
24         int ans=0;
25         memset (visit,0,sizeof visit);
26         int pos=1;visit[1]=1;
27         for (int i=1;i<=n;i++)
28             low[i]=map[pos][i];
29         int mi=INF;
30         for (int i=1;i<n;i++){
31             mi=INF;
32             for (int j=1;j<=n;j++)
33                 if (visit[j]==0&&low[j]<mi){
34                     mi=low[j];pos=j;
35                 }
36             ans+=mi;visit[pos]=1;
37             for (int j=1;j<=n;j++)
38                 if (!visit[j])
39                     low[j]=min(low[j],map[pos][j]);
40         }
41         printf ("%d\n",ans);
42     }
43     return 0;
44 }

 

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

标签： class style Go log si for it ios ca class style Go log si for it ios ca

相关文章

随机文章

您可能还喜欢

您可能还喜欢