hdu 1102 （最小生成树kruskal算法--并查集，prim死活过不了）

心已赠人 2022-09-18 08:54 122阅读 0赞

http://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
    */