蓝桥杯 历届试题 城市建设 （最小生成树）

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define INF 0xfffffff
int n,m,k;
int pre[10005];
struct s
{
	int u,v,w;
}edge[1000005];
int cmp(const void *a,const void *b)
{
	return (*(struct s *)a).w-(*(struct s *)b).w;
}
int find(int x)
{
	if(x==pre[x])
		return x;
	return pre[x]=find(pre[x]);
}
void init(int n)
{
	int i;
	for(i=0;i<=n;i++)
	{
		pre[i]=i;
	}
}
int ku(int k)
{
	int sum=0,i;
	for(i=0;i<k;i++)
	{
		int u=edge[i].u;
		int v=edge[i].v;
		int w=edge[i].w;
		int fa=find(u);
		int fb=find(v);
		if(fa!=fb||w<0)
		{
			sum+=w;
			pre[fa]=fb;
		}
	}
	return sum;
}
int main()
{
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		int i,j;
		init(n);
		for(i=0;i<m;i++)
		{
			int u,v,w;
			scanf("%d%d%d",&u,&v,&w);
			edge[i].u=u;
			edge[i].v=v;
			edge[i].w=w;
		}
		k=m;
		for(i=1;i<=n;i++)
		{
			int cost;
			scanf("%d",&cost);
			if(cost!=-1)
			{
				edge[k].u=0;
				edge[k].v=i;
				edge[k++].w=cost;
			}
		}
		for(i=0;i<m;i++)
		{
			int fa=find(edge[i].u);
			int fb=find(edge[i].v);
			if(fa!=fb)
				pre[fa]=fb;
		}
		for(i=2;i<=n;i++)
		{
			if(find(1)!=find(i))
			{
				break;
			}
		}
		int temp;
		if(i==n+1)
		{
			init(n);
			qsort(edge,m,sizeof(edge[0]),cmp);
			temp=ku(m);
			init(n);
			qsort(edge,k,sizeof(edge[0]),cmp);
			int ans=ku(k);
			if(ans>temp)
				printf("%d\n",temp);
			else
				printf("%d\n",ans);
			continue;
		}
		init(n);
		qsort(edge,k,sizeof(edge[0]),cmp);
		int ans=ku(k);
		printf("%d\n",ans);
	}
}