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

数组开小了!!!附代码!!!克鲁斯卡尔模板算法!!!

Posted by chenxuan123456789 at 2012-09-11 23:03:51 on Problem 1861
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int father[15010],flag[15010];
typedef struct node
{
	int c1;
	int c2;
	int d;
}Node;
Node point[15010];
int cmp(const void *_a,const void *_b)
{
	Node *a=(Node*)_a;
	Node *b=(Node*)_b;
	return a->d-b->d;
}
void init(int n)
{
	int i;
	for(i=1;i<=n;i++)
	father[i]=i;
}
int dfs(int x)
{
	return x==father[x]?x:dfs(father[x]);
}
int merge(int a,int b)
{
	int c1=dfs(a);
	int c2=dfs(b);
	if(c1==c2)
		return 0;
	else
	{
		if(c1>c2)
			father[c1]=c2;
		else
			father[c2]=c1;
		return 1;
	}
}
int main()
{
	int n,m,i,j,sum,count,mlen;
	scanf("%d %d",&n,&m);
	for(i=1;i<=m;i++)
	scanf("%d %d %d",&point[i].c1,&point[i].c2,&point[i].d);
	qsort(point+1,m,sizeof(point[0]),cmp);
	init(n);
	count=0;
	sum=0;
	mlen=0;
	memset(flag,0,sizeof(flag));
	for(i=1;i<=m;i++)
	{
		if(merge(point[i].c1,point[i].c2))
		{
			flag[i]=1;
			if(point[i].d>mlen)
			mlen=point[i].d;
			sum+=point[i].d;
			count++;
		}
		if(count==n-1)
			break;
	}
	printf("%d\n",mlen);
	printf("%d\n",count);
	for(i=1;i<=m;i++)
		if(flag[i])
			printf("%d %d\n",point[i].c1,point[i].c2);
		return 1;
}
	



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