hdu 1102 (最小生成树kruskal算法--并查集,prim死活过不了)

https://acm.hdu.edu.cn/showproblem.php?pid=1102



#include"stdio.h"
#include"algorithm"
#include"iostream"
#include"string.h"
using namespace std;

typedef struct node
{
	int v1,v2;
	int length;
}node;
node bian[6000];
int father[110],k;
bool cmp(node a,node b)
{
	if(a.length<b.length)
		return true;
	return false;
}

int search(int x)//寻找父亲结点 
{
	while(father[x]!=x)
		x = father[x];
	return father[x];
}
int n;
void kulusi()//郁闷了 用prime算法死活过不了 
{
		int i,length;
		for(i=1;i<=n;i++)	father[i] = i;	
		length = 0;

		for(i=0;i<k;i++)
		{
			if(search(bian[i].v1)!=search(bian[i].v2))//如果两个点的父亲结点相同的话就相通不用修路了 
			{
				length += bian[i].length;
				father[search(bian[i].v1)] = bian[i].v2;
			}	
		}
		printf("%d\n",length);		
}

int main()
{
	int i,j,q,a,b,tmp;
	while(~scanf("%d",&n)){
		k=0;
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++){
				scanf("%d",&tmp);
				if(j>=i){
					bian[k].v1 = i;
					bian[k].v2 = j;
					bian[k].length = tmp;
					k++;
				}
			} 
		scanf("%d",&q);
		for(i=0;i<q;i++){
			scanf("%d%d",&a,&b);
			bian[k].v1=a;
			bian[k].v2=b;
			bian[k].length = 0;
			k++;
		}
		sort(bian,bian+k,cmp);
		kulusi();
	}
	
	return 0; 
}
/*
3
0 990 692
990 0 179
692 179 0
1
1 2
3
0 990 692
990 0 179
692 179 0
0
*/