poj 最小生成树 prim Kruskal 1251 1287 2396

poj1251

用的是Kruskal算法 以及并查集

#include "iostream"
using namespace  std;
#define  maxsize 110
typedef struct Edge
{
	int weight;//权值
	int  node1;//顶点
	int node2;//顶点
} Edge;

Edge e[maxsize];
int vis[maxsize];

int   putIn(int n)
{


	//输入
	char ch;
	int num;
	char ch1;
	int t;
	int i,j,k=0;
	for (i=0;i<n-1;i++)
	{
		cin>>ch>>num;
		for (j=0;j<num;j++)
		{
			cin>>ch1>>t;
			e[k].weight=t;
			e[k].node1=ch-65;
			e[k].node2=ch1-65;
			k++;
		}	
	}


	return  k;//边的个数
}

int cmp( const void *a ,const void *b)
{
	
	Edge *aa=(Edge*)a;
	Edge *bb=(Edge*)b;

	return aa->weight>bb->weight?1:-1;
}

void union_node(int i,int len)
{

	//将e[i].node1的集合并入e[i].node2的集合
	int j;
	int t=vis[e[i].node1];//要先将vis[e[i].node1保存下来 因为循环中会改变值
	for (j=0;j<len;j++)
	{
		if (vis[j]==t)
		{
			vis[j]=vis[e[i].node2];
		}
	}
}

int Kruskal(int len,int n)
{

	int i,j;
	int ans=0;

	//vis数组用做并查集
	for (i=0;i<n;i++)//i<len是错的  应该是村庄个数
	{
		vis[i]=i;//表示第i个元素属于第i个集合
	}

	
	for (i=0;i<len;i++)
	{

		if (vis[e[i].node1]!=vis[e[i].node2])//如果该边的两个顶点在不同的集合
		{
			//将两点并入一个集合
			union_node(i,len);
			//累加权值
			ans+=e[i].weight;
		}
	}

	return  ans;

}
int main()
{
	
	int n;
	int i,j;
	while(cin>>n)
	{
		
		if(n==0)
			break;
		int len=putIn(n);
	
		//按权值从小到大排序
		qsort(e,len,sizeof(e[0]),cmp);
			

		//Kruskal算法生成最小生成树
		int ans=Kruskal(len,n);
		
		//输出结果
		cout<<ans<<endl;
		
	}
	return 0;
}

 

poj 1287

 

prim 

 

#include "iostream"
using namespace  std;
#define MAXSIZE 1500
#define MAX 99999999
int map[MAXSIZE][MAXSIZE];
int vis[MAXSIZE];
int temp[MAXSIZE];
int main()
{
	int n,m;
	while (1)
	{
		scanf("%d",&n);
		if (n==0)
		{
			break;
		}
		scanf("%d",&m);

		int  ans=0;
		int i,j;
		for (i=0;i<n;i++)
		{
			for (j=0;j<n;j++)
			{
				map[i][j]=MAX;
			}
		}
		for (i=0;i<m;i++)
		{
			int t1,t2,w;
			scanf("%d%d%d",&t1,&t2,&w);
			if (w<map[t1-1][t2-1])
				map[t1-1][t2-1]=w;

		}
		for (i=0;i<m;i++)
		{
			for (j=0;j<m;j++)
			{
				if (map[i][j]<map[j][i])
				{
					map[j][i]=map[i][j];
				}
			}
		}
		memset(vis,0,sizeof(vis));
		for (j=0;j<n;j++)
		{
			temp[j]=MAX;
		}
		i=0;
		for (j=0;j<n;j++)
		{
			if (map[i][j]!=0)
				if (map[i][j]<temp[j])
				{
					temp[j]=map[i][j];
				}
		}
		vis[0]=1;
		while (i<n-1)
		{
			
			//找最小的边
			int min=MAX;
			int minindex=0;
			for (j=0;j<n;j++)
			{
				if (vis[j]==1)
				{
					continue;
				}
				if (min>temp[j])
				{
					min=temp[j];
					minindex=j;
				}
			}
			
			
			//把最小的边的顶点加入集合 
			vis[minindex]=1;
			
			//更新temp
			for (j=0;j<n;j++)
			{
				if (map[minindex][j]!=0&&vis[j]!=1)
					if (map[minindex][j]<temp[j])
					{
						temp[j]=map[minindex][j];
					}
			}
			
			
			ans+=min;
			i++;
			
			
		}
		printf("%d\n",ans);

	}
	
	return 0;	
}

 

 

poj 2395 

与1251一样

#include "iostream"
using namespace  std;
#define  maxsize 10015
typedef struct Edge
{
	int weight;//权值
	int  node1;//顶点
	int node2;//顶点
} Edge;

Edge e[maxsize];
int vis[maxsize];

void   putIn(int n,int m)
{

	int num=0;
	//输入
	for (int i=0;i<m;i++)
	{
		int  k1,k2,w;
		cin>>k1>>k2>>w;
		e[num].node1=k1;
		e[num].node2=k2;
		e[num].weight=w;
		num++;
	}

	//return  m;//边的个数
}

int cmp( const void *a ,const void *b)
{
	
	Edge *aa=(Edge*)a;
	Edge *bb=(Edge*)b;

	return aa->weight>bb->weight?1:-1;
}

void union_node(int i,int len)
{

	//将e[i].node1的集合并入e[i].node2的集合
	int j;
	int t=vis[e[i].node1];//要先将vis[e[i].node1保存下来 因为循环中会改变值
	for (j=0;j<len;j++)
	{
		if (vis[j]==t)
		{
			vis[j]=vis[e[i].node2];
		}
	}
}

int Kruskal(int m,int n)
{

	int i,j;
	int ans=0;

	//vis数组用做并查集
	for (i=0;i<n;i++)//i<len是错的  应该是村庄个数
	{
		vis[i]=i;//表示第i个元素属于第i个集合
	}

	int  count=0;
	int max=0;
	for (i=0;i<m;i++)
	{
		
		if (vis[e[i].node1]!=vis[e[i].node2])//如果该边的两个顶点在不同的集合
		{
			//将两点并入一个集合
			union_node(i,m);
			//累加权值
			ans+=e[i].weight;
			if(max<e[i].weight)
				max=e[i].weight;
			count++;
		}
		if (count==n-1)
		{
			break;
		}
	}

	return  max;

}
int main()
{
	
	int n,m;
	int i,j;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
	//	cin>>n>>m;
		//cin>>m;
		putIn(n,m);
	
		//按权值从小到大排序
		qsort(e,m,sizeof(e[0]),cmp);
			

		//Kruskal算法生成最小生成树
		int ans=Kruskal(m,n);
		
		//输出结果
		cout<<ans<<endl;
		
	}
	return 0;
}