kruskal求MST

//6613058 Xredman 2485 Accepted 412K 235MS C++ 1727B 2010-03-23 11:58:24 
/*
Kruskal MST模板：适用于无向图 
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX_SIZE = 502;

typedef struct
{
	int parent;
	int height;
}Node;

typedef struct Edge 
{
	int u, v, dist;
	Edge(){};
	Edge(int tu, int tv, int tdist):u(tu),v(tv),dist(tdist){};
	bool operator<(const Edge edge) const
	{
		return dist < edge.dist;
	}
}Edge;

Edge edge[MAX_SIZE * MAX_SIZE];

Node UFSet[MAX_SIZE];

int nEdge;

void make_set(int n)
{//初始化并查集 
	for(int i = 0; i < n; i++)
	{
		UFSet[i].parent = i;
		UFSet[i].height = 1;
	}
} 

int find(int x)
{//O(n) 
	while(x != UFSet[x].parent)
		x = UFSet[x].parent;
	return x;
}

bool merge(int x, int y)
{//O(1)
	x = find(x);
	y = find(y);
	if(x == y)
		return false;
	if(UFSet[x].height == UFSet[y].height)
	{
		UFSet[y].parent = x;
		UFSet[x].height++;
	}else if(UFSet[x].height > UFSet[y].height)
	{
		UFSet[y].parent = x;
	}else
	{
		UFSet[x].parent = y;
	}
}

void readin(int n)
{
	nEdge = 0;
	int i, j;
	for(i = 0; i < n; i++)
	{
		for(j = 0; j < n; j++)
		{
			if(i < j)
			{
				edge[nEdge].u = i;
				edge[nEdge].v = j;
				scanf("%d", &edge[nEdge++].dist);
			}
			else
			{
				scanf("%*d");
			}
		}
	}	
	make_set(n);
}

int kruskal()
{
	int i, maxx = 0;;
	int x, y;
	sort(edge, edge + nEdge);

	for(i = 0; i < nEdge; i++)
	{
		x = find(edge[i].u);
		y = find(edge[i].v);
		if(x != y)
		{
			merge(x, y);
			maxx = edge[i].dist > maxx ? edge[i].dist : maxx;
		}
	}
	return maxx;
}

int main()
{
	int n;
	int T;
	scanf("%d", &T);
	while(T-- && scanf("%d", &n))
	{
		readin(n);
		printf("%d\n",kruskal());
	}
	return 0;
} 

• 相关文章
• 全局相关文章