还是畅通工程

  

   3
1 2 1
1 3 2
2 3 4
4
1 2 1
1 3 4
1 4 1
2 3 3
2 4 2
3 4 5
0
  

  

   3
5


   

    

     Hint
    
Hint
   
    
Huge input, scanf is recommended.
  

解题思路：一道简单的水题，因为刚开始学习图论，刷水题感觉可以收获更多，kruskal算法主要是将每一个边的两端点及权值存入一个结构体中，然后由小到大的顺序排序，从最小的边开始选择，如果两个端点没有公共的祖先，则合并，并加上其权值；

本题注意set[]数组的初始化，我就错在这两次

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,set[101];

struct node
{
	int u,v,w;//u,v,表示村庄，w表示两者之间的费用 
}edge[101*101];

int cmp(const node &a,const node &b)
{
	return a.w<b.w;
}

int find(int x)
{
	while(set[x]!=x)
		x=set[x];
	return x;
}

int kruskal()
{
	int ans=0,x,y;
	sort(edge+1,edge+(n*n-n)/2+1,cmp);
	for(int i=1;i<=(n*n-n)/2;i++)
	{
		x=edge[i].u;
		y=edge[i].v;
		x=find(x);
		y=find(y);
		if(x!=y)
		{
			set[y]=x;
			ans+=edge[i].w ;
		}
	}
	return ans;
}

int main()
{
	while(scanf("%d",&n),n)
	{
		for(int i=0;i<=n;i++)
			set[i]=i;
		for(int i=1;i<=(n*n-n)/2;i++)
			scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);
		printf("%d\n",kruskal());
	}
	return 0;
}

另外本题的prim算法：prim算法和kruskal算法差不多，所不同的是prim算法始终有一颗子树的存在，然后向上加边，每次要保证加的边是最小值

代码：

#include<cstdio>
#include<cstring>
using namespace std;
int mp[105][105],n;
const int INF = 0x7fffffff;

int prim()
{
	int ans=0,min,cnt;
	int lowcost[105],vis[105];
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=n;i++)
		lowcost[i]=mp[1][i];
	vis[1]=1;
	for(int i=1;i<n;i++)
	{
		min = INF,cnt=-1;
		for(int j=1;j<=n;j++)
			if(vis[j]==0&&min>lowcost[j])
			{
				min=lowcost[j];
				cnt=j;
				//printf("j=%d,cnt=%d,min=%d\n",j,cnt,min);
			}
		if(cnt==-1) return -1;
		//printf("%d\n",min);
		ans+=min;
		vis[cnt]=1;
		for(int j=1;j<=n;j++)
		{
			if(vis[j]==0 && lowcost[j] > mp[cnt][j]) 
				lowcost[j]=mp[cnt][j];
		}
	}
	return ans;
}

int main( )
{
	while(scanf("%d",&n),n)
	{
		int a,b,c;
		for(int i=1;i<n;i++)
			for(int j=i;j<=n;j++)
				mp[i][j]=mp[j][i]=INF;
		for(int i = 1; i <= n*(n-1)/2 ; i++)
		{
			scanf("%d%d%d",&a,&b,&c);
			mp[a][b]=mp[b][a]=c;
		}
		printf("%d\n",prim());
	}
}