hdoj1879——最小生成树的变形

这回AC了,上回对克鲁斯卡尔理解不深,今天想着想着想到了。
题意:给你n个点,告诉你这些点之间的距离,即(n-1)*n/2条边的边权。其中一些边已经有了,问再建一些边使图连通,最小代价是多少?
思路:读入所有边,已经建的边的两个顶点并入一个集合,读入的同时,是未建立的边,则保存入edge[]数组,否则只是合并顶点。这样数据对毕,也就得到了(假设)count个集合(可以把一个集合中的所有点看成一个点),那么连通这张图需要count-1条边。接下来就是一般的克鲁斯卡尔了。
总的思想其实就是把已经连通的点看成一个点,这样就形成了一个新的图。对这个图求最小生成树即可。

hdoj1102——最小生成树

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1102
第一次写MST,小问题不断,开始的时候这道题是这么想的,因为已经修好的路不一定是原来最小生成树中的路,所以先把已经修好路的顶点加入A集合(最小生成树的集合),(假设有count个顶点已经修好路)并更新dist数组。那么接下来只要用prim算法对剩下的(n-count)个顶点继续构造最小生成树即可。但是不知何故,15MS时WA。。
看了一篇解题报告,发现他的做法是把已修好路的顶点之间的距离设为0,然后求出整张图的最小生成树。仔细想想,确实这样做思路更简单,而且代码实现也简单。因为已修好路的顶点间距离设为0,则接下来构造MST时可以保证这些修好的路必定在最小生成树中。(一种情况除外,当已经修好的路数量大于(n-1)时,会有几条长度为0的边被舍去,但是答案终归是0,并不影响正确性)
贴上AC代码:

最小生成树——prim算法(邻接矩阵)

#include<stdio.h>
#include<stdlib.h>
typedef struct Dist{
	int pre;//这个点是连到集合A中哪个点的
	int dist;
}Dist;
Dist dist[n];//顶点数
int map[n][n];
int visit[n];
void prim(int dist[],int map[][])
{
	int i,j;
	dist[1].dist=0;
	for(j=2;j<=n;j++)
	{
		dist[j].dist=map[1][j];
		dist[j].pre=1;
		visit[j]=false;
	}
	visit[1]=true;
	for(i=1;i<=n-1;i++)
	{
		int min=INT_MAX;
		int k=0;
		for(j=1;j<=n;j++)
		{
			if(!visit[j] && dist[j].dist<min)
			{
				min=dist[j].dist;
				k=j;
			}
		}
		if(k==0) return;//无法从第一个结点扩展,即图不连通,返回
		visit[k]=true;
		for(i=1;i<=n;i++)
			if(!visit[i] && map[k][i]!=INT_MAX && map[k][i]<dist[i].dist)
			{
				dist[i].dist=map[k][i];
				dist[i].pre=k;
			}
	}
	return;
}
int main()
{




system("pause");
return 0;
}