CCF-CSP-201412-4 最优灌溉(100分)

题目:

解题思路：

• 这道题要求从一号田开始，用最小的花费将所有的点连起来，是一道典型的最小生成树问题
• 这道最小生成树问题可以采用Kruskal算法或者Prim算法，下面我给出两种算法分别的实现方法

满分代码：

第一种：Kruskal算法

运行消耗

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;

const int N =1002;
const int M =100002;
int n,m;

struct edge{
	int x,y;
	int cost;
}a[M];//边 

int father[N];//并查集

int findfather(int x)
{
	int a=x;
	int z;
	while(x!=father[x])
	{
		x=father[x];
	}
	
	//路径压缩
	while(a!=father[a])
	{
		z=a;
		a=father[a];
		father[z]=x;	
	}
	return x;	
} 

bool compare(edge a,edge b){return a.cost<b.cost;}

int kruskal(int n,int m)
{
	int sum=0,edgenum=0;
	for(int i=0;i<n;i++)
	{
		father[i]=i;
	}//初始化并查集
	sort(a,a+m,compare);//排序
	for(int i=0;i<m;i++)
	{
		int fax=findfather(a[i].x);
		int fay=findfather(a[i].y);
		if(fax!=fay)
		{
			father[fax]=fay;
			sum+=a[i].cost;
			edgenum++;
			if(edgenum==n-1)break;
		}
	}
	return sum;	
}

int main()
{
	cin>>n>>m;//初始化输入 		
	for(int i=0;i<m;i++){cin>>a[i].x>>a[i].y>>a[i].cost;}//初始化输入边	
	cout<<kruskal(n,m);//最小生成树 KrusKal算法 		
	return 0;
}

第二种：Prim算法:

运行消耗

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int M=100001;
const int N=1001;
const int INF=100000;

int n,m;
int a[N][N];
bool visit[N]={};//节点是否已经被访问 
int dist[N];//顶点与集合的距离 
 
int prim()
{
	fill(dist,dist+N,INF);//赋初值
	dist[1]=0;
	int sum=0;//总费用
	
	//找最小距离
	for(int i=1;i<=n;i++)
	{
		int minx=-1;
		int mini=INF;
		
		for(int j=1;j<=n;j++) 
		{
			if(visit[j]==false&&dist[j]<=mini)
			{
				minx=j;
				mini=dist[j];
			}
		}//找到与当前集合距离最近的节点 
		
		
		if(minx!=-1)//找到符合条件的点
		{
			visit[minx]=true;//第minx号点已经访问过了
		    sum+=dist[minx];//加入最小生成树,该点加入集合 
		}
		
		
		
		//更新剩余的点到集合的最短距离
		for(int y=1;y<=n;y++)
		{
			if(visit[y]==false&&a[minx][y]!=INF&&a[minx][y]<dist[y])
			{
				dist[y]=a[minx][y];
			}
		} 		 			
	} 	
	return sum;	 
} 


int main()
{
	int i,j,k;
	cin>>n>>m;
	fill(a[0],a[0]+N*N,INF);//初始化 
	
	while(m--)
	{
		cin>>i>>j>>k;
		a[i][j]=a[j][i]=k;
	}
	
	cout<<prim();	
	return 0;
}