样例输入  Sample Input

4

0  4  9 21

4  0  8 17

9  8  0 16

21 17 16  0

样例输出  Sample Output

28

Prim算法

/* 作者:thmyl 题目:p1078 最小生成树 */ //邻接矩阵 #include<iostream> #include<cstdio> #include<cstring> using namespace std; int n,map[110][110],ans,dis[110]; bool vis[110]; void Prim(){ memset(dis,127/3,sizeof(dis)); dis[1]=0; for(int i=1;i<=n;i++){ int k=0; for(int j=1;j<=n;j++){ if(!vis[j]&&(dis[j]<dis[k])){ k=j; } } ans+=dis[k]; vis[k]=1; for(int j=1;j<=n;j++){ if(!vis[j]) dis[j]=min(dis[j],map[k][j]); } } } int main(){ memset(map,127/3,sizeof(map)); scanf("%d",&n); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&map[i][j]); Prim(); printf("%d",ans); } 邻接矩阵 #include<iostream> #include<cstdio> #include<cstring> using namespace std; int n,num,head[220],ans,dis[110]; bool vis[110]; struct node{ int to,v,pre; }e[22000]; void Insert(int from,int to,int v){ e[++num].pre=head[from]; e[num].to=to; e[num].v=v; head[from]=num; } void Prim(){ memset(dis,127/3,sizeof(dis)); dis[1]=0; for(int i=1;i<=n;i++){ int minn=0x7fffffff,k=0; for(int j=1;j<=n;j++){ if(!vis[j]&&dis[j]<minn){ minn=dis[j]; k=j; } } if(minn==0x7fffffff)break; vis[k]=1; for(int j=head[k];j;j=e[j].pre){ int f=e[j].to; if(!vis[f]) dis[f]=min(dis[f],e[j].v); } } for(int i=1;i<=n;i++)ans+=dis[i]; } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ int x;scanf("%d",&x); if(i!=j)Insert(i,j,x); } } Prim(); printf("%d",ans); } 边表