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

我的47ms,只用了路径压缩这一个优化

Posted by fyq at 2010-05-08 22:02:24 on Problem 2395
In Reply To:我的也63ms^_^ Posted by:nazgul1991 at 2010-04-06 16:07:28
/*Source Code
Problem: 2395		User: fyq
Memory: 488K		Time: 47MS
Language: G++		Result: Accepted
*/

#include <cstdio>
#define maxn 3001
#define maxm 15001

using namespace std;

typedef struct node
{
	int x,y,cost;
}node;

int fa[maxn+1];
node g[maxm+1];
int n,m;

void qsort(int l,int r)
{
	int i = l,j = r;
	int m = g[(i+j)/2].cost;
	node t;
	while (i<=j)
		{
			while (g[i].cost<m) i++;
			while (m<g[j].cost) j--;
			if (i<=j)
				{
					t = g[i]; g[i] = g[j]; g[j] = t;
					i++; j--;
				}
		}
	if (i<r) qsort(i,r);
	if (l<j) qsort(l,j);
}

int find(int x)
{
	int k = x;
	while (fa[k]!=-1)
		k = fa[k];
	int t = x;
	int temp;
	while (t!=k)
		{
			temp = fa[t];
			fa[t] = k;
			t = temp;
		}
	return k;
}

int kruskal()
{
	int ans;
	for (int i=1;i<=n;i++)
		fa[i] = -1;
	int total = 0;
	for (int i=1;i<=m;i++)
		{
			int ancx = find(g[i].x);
			int ancy = find(g[i].y);
			if (ancx!=ancy)
			{
					ans = g[i].cost;
					fa[ancx] = fa[ancy];
					total ++;
				}
		}
	return ans;
}

int main()
{
	scanf("%d%d",&n,&m);
	int a,b,c;
	for (int i=1;i<=m;i++)
		{
			scanf("%d%d%d",&a,&b,&c);
			g[i].x = a; g[i].y = b; g[i].cost = c;
		}
	qsort(1,m);	
	printf("%d\n",kruskal());
	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