POJ 1258 Agri-Net

这里我Krustral和Prim算法都用了。

Krustral算法

#include<iostream>
#include<cstdio>
#include<cstring>
#include<functional>
#include<algorithm>
using namespace std;
int n,m,sum;
int k;
int fa[1005];
struct node
{
	int from,to;
	int cost;
}e[30005];
int cmp(struct node a,struct node b){return a.cost<b.cost;}
void init()
{
	int i;
	for(i=1;i<=n*n;i++)
		e[i].from=e[i].to=e[i].cost=0;

	for( i=1;i<=n;i++)
		fa[i]=i;
	sum=0;
}
int getfa(int x)
{
	if(x==fa[x])
		return x;
	else
		return x=getfa(fa[x]);
}
int merge(int u,int v)
{
	int t1,t2;
	t1=getfa(u);
	t2=getfa(v);
	if(t1!=t2)
	{
		fa[t1]=t2;
		return 1;
	}
	return 0;
}
int main()
{
	int i,j,t1,t2,t3;
	while(scanf("%d",&n)!=EOF)
	{
		init();
		k=1;
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=n;j++)
			{
				scanf("%d",&t1);
				if(j<i)
					continue;
				e[k].from=i;
				e[k].to=j;
				e[k].cost=t1;
				k++;
			}
		}
		k--;
		sort(e+1,e+k+1,cmp);
 
		for(i=1;i<=k;i++)
		{
			if(merge(e[i].from,e[i].to))
				{
					//printf("From=%d To=%d Cost=%d\n",e[i].from,e[i].to,e[i].cost);
					sum+=e[i].cost;
				}
		}
		printf("%d\n",sum);
	}
}
/*
4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0
5
0 4 9 21 26
4 0 8 17 25
9 8 0 16 34
21 17 16 0 21
26 25 34 21 0
*/

Prim算法

//邻接矩阵存储图
//需要给定起点u0
#include<iostream>
#include<cstdio>
#include<cstring>
#include<functional>
#include<algorithm>
#define inf 0x3f3f3f3f
#define maxn 1000
int n,m;
int edge[maxn][maxn];//邻接矩阵存储图
int lowcos[maxn];//生成树到各个点的距离
int nearvex[maxn];//lowcos的起点
void init()//初始化操作，
{
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(i==j)
				edge[i][j]=0;
			else
				edge[i][j]=inf;
}
void prim(int u0)//Prim生成树算法，u0为给定起点
{
	int i,j;
	int sum=0;
	for(i=1;i<=n;i++)//初始化lowcos数组
	{
		lowcos[i]=edge[u0][i];
		nearvex[i]=u0;
	}
	nearvex[u0]=-1;//把起点加入生成树集合S
	for(i=1;i<n;i++)//最多N-1轮，N个点构成生成树只需要N-1条边
	{
		int Min=inf;
		int v=-1;
		for(j=1;j<=n;j++)//找权值最小的且未加入生成树的边
		{
			if(nearvex[j]!=-1&&lowcos[j]<Min)
			{
				v=j; Min=lowcos[j];
			}
		}
		if(v!=-1)//v==-1的时候代表找不到，结束生成树算法
		{
			//printf("%d %d %d\n",nearvex[v],v,lowcos[v]);//起点，终点，权值
			nearvex[v]=-1;//加入集合S
			sum+=lowcos[v];
			for(j=1;j<=n;j++)//跟新Lowcos数组
			{
				if(nearvex[j]!=-1&&edge[v][j]<lowcos[j])
				{
					lowcos[j]=edge[v][j];
					nearvex[j]=v;
				}
			}
		}
	}
	printf("%d\n",sum);
}

int main()
{
	int i,j;
	int u,v,w;
	while(scanf("%d",&n)!=EOF)
	{
		init();
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
				scanf("%d",&edge[i][j]);
		prim(1);//需要给定起点
	}
	return 0;
}