POJ-2421-Constructing Roads（最小生成树 普利姆）

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
#define N 110
#define M 0x3f3f3f3f//用一个大值表示两点不通 

int map[N][N];
int vis[N],dst[N];//vis标已加入MST的点，dst存放各点到MST的最小距离 
int n,q;

void init()//初始图 
{
	int i,j;
	
	for (i=0;i<N;i++)
	{
		for (j=0;j<N;j++)
		{
			i==j?map[i][j]=0:map[i][j]=M;//自己到自己的点距离为0 
		}
	}
	memset(vis,0,sizeof(vis));
	memset(dst,0,sizeof(dst));
}

void prime()
{
	int ans=0,i,min,j,k,point;
	
	vis[1]=1;//1放入MST 
	for (i=1;i<=n;i++)
	{
		dst[i]=map[i][1];//dst初始化 
	}
	
	for (i=1;i<=n;i++)
	{
		min=M;
		for (j=1;j<=n;j++)//找距MST最近的点 
		{
			if (vis[j]==0&&min>dst[j])
			{
				min=dst[j];
				point=j;
			}
		}
		if (min==M)//没有连通点 
		{
			break;
		 }
		 
		vis[point]=1;//把距MST最近的点加入MST 
		ans=ans+dst[point];
		
		for (k=1;k<=n;k++)//更新各点到MST的最小距离 
		{
			if (vis[k]==0&&dst[k]>map[k][point])
			{
				dst[k]=map[k][point];
			} 
		}
	}
	printf("%d\n",ans);
}

int main()
{
	int i,j,x,y;
	
	scanf("%d",&n);
	init();
	for (i=1;i<=n;i++)
	{
		for (j=1;j<=n;j++)
		{
			scanf("%d",&map[i][j]);
		}
	}
	
	scanf("%d",&q);
	for (i=0;i<q;i++)
	{
		scanf("%d%d",&x,&y);//已连通的两点权为0 
		map[x][y]=0;
		map[y][x]=0;
	}
	
	prime();
	
	return 0;
}