很简单的一道题目,就主要是吧已经修建成功的赋成map[i][j]就行了.
贴出代码:
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <math.h> #define inf 0x3fffffff int N,M;// N represents the number of points,and M stands for the number of that has been built points; int map[105][105]; int dis[105]; int visit[105]; int prim() { for(int i=1;i<=N;i++) dis[i]=inf; dis[1]=0; for(int j=1;j<=N;j++) { int t=inf,pos; for(i=1;i<=N;i++) { if(!visit[i]&&t>dis[i]) { t=dis[i]; pos=i; } } visit[pos]=1; for(i=1;i<=N;i++) { if(!visit[i]&&dis[i]>map[pos][i]&&map[pos][i]!=0x3f3f3f3f) { dis[i]=map[pos][i]; } } } int temp=0; for(int k=1;k<=N;k++) { temp+=dis[k]; } return temp; } int main() { int a,b; while(scanf("%d",&N)!=EOF) { memset(map,0x3f,sizeof(map)); memset(visit,0,sizeof(visit)); for(int i=1;i<=N;i++) { for(int j=1;j<=N;j++) { scanf("%d",&map[i][j]); } } scanf("%d",&M); for(i=1;i<=M;i++) { scanf("%d%d",&a,&b); map[a][b]=0; map[b][a]=0; } int ans=prim(); printf("%d\n",ans); } return 0; }