Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

气死我了,qsort错了害我WA了无数次,现将修改代码公开

Posted by bjtu1 at 2009-02-17 20:03:28 on Problem 2485
AC  266ms
/*By bjtu1*/
/*2-17-2009*/
/*language:c++*/
#include<stdio.h>
#include<stdlib.h>
#include<memory.h>
#define MAX 501


int father[MAX];
int rank[MAX];

typedef struct Node{
	int x,y;
	int len;
}Node;
Node arr[MAX*MAX];

int cmp(const void *e1,const void *e2){
	return (*(Node *)e1).len>(*(Node *)e2).len?1:-1;
};


void Make(int n){
	int i;
	for(i=1;i<=n;i++){
		father[i]=i;
		rank[i]=0;
	}
};


int Find(int v){
	if(father[v]==v)
		return v;
	else {
		father[v]=Find(father[v]);
		return father[v];
	}
};

void Uion(int u,int v){
	if(rank[Find(u)]>rank[Find(v)]){
		father[Find(v)]=Find(u);
		rank[Find(u)]+=rank[Find(v)];
	}
	else {
			father[Find(u)]=Find(v);
			rank[Find(v)]+=rank[Find(u)];
	}
};


int main()
{
	int i,j,k;
	int max,a;
	int T;
	int n;

	scanf("%d",&T);
	while(T){
		memset(arr,0,sizeof(arr));
		scanf("%d",&n);
		Make(n);
		k=0;
		for(i=0;i<n;i++){
			for(j=0;j<=i;j++)
				scanf("%d",&a);
			for(j=i+1;j<n;j++){
				scanf("%d",&arr[k].len);
				arr[k].x=i;
				arr[k].y=j;
				k++;
			}
		}
		qsort(arr,k,sizeof(arr[0]),cmp);
		i=0;
		j=0;
		while(i<(n-1)&&j<k){
			if(Find(arr[j].x)!=Find(arr[j].y)){
				Uion(arr[j].x,arr[j].y);
				max=j;
				i++;
			}
			j++;
		}

		printf("%d\n",arr[max].len);
		T--;
	}
	return 0;
}


Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator