kruskal.cpp

西电的VC++课上的几个通用模板,完全是可用的

#include <iostream>
#include <fstream>
#include <algorithm>
#include "UnionFindSet.h"

using namespace std;

fstream fin("in.txt",ios::in);
#define cin fin
#define MAX 512

struct Edge
{
	int b,e,w;
}*edge,*path;

bool small(Edge a, Edge b)
{
	return a.w<b.w;
}

int edgeNum;
int vertexNum;

UnionFindSet unionFindSet;

void Kruskal();
void Read();
void Print();

int main()
{
	Read();
	Kruskal();
	Print();
	delete edge;
	delete path;
	return 0;
}

void Kruskal()
{
	unionFindSet.Initialize(50000);
	sort(edge,edge+edgeNum,small);

	int a,b;
	int j=0;
	for (int i=0; i<edgeNum; i++)
	{
		if (j == vertexNum)
			break;
		
		a = unionFindSet.Find(edge[i].b);
		b = unionFindSet.Find(edge[i].e);

		if (a!=b)
		{
			unionFindSet.SetUnion(a,b);
			path[j++] = edge[i];
		}
	}
}

void Read()
{
	cin>>vertexNum;
	cin>>edgeNum;
	path = new Edge[vertexNum];
	edge = new Edge[edgeNum];
	int i;
	for(i=0; i<edgeNum; i++)
		cin>>edge[i].b>>edge[i].e>>edge[i].w;
}

void Print()
{
	//sort(path, path+vertexNum, small);
	cout<<path[vertexNum-1].w<<endl;
	cout<<vertexNum-1<<endl;
	for(int i = 0; i < vertexNum; i++)
	{
		cout<<path[i].b<<' '<<path[i].e<<endl;
	}
}