学步园

  水题一道，关键是理解题目为最小生成树。纯粹为了复习并查集和Kruscal最小生成树。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


class Edge
{
public:
	int nId1,nId2;
	int length;
};

class LinkNode
{
public:
	LinkNode()
	{
		nodeID=-1;
		length=-1;
		nextNode=NULL;
	}
	int nodeID;
	int length;
	LinkNode* nextNode;
};

class Node
{
public:
	Node()
	{
		nodeID=0;
		parent=NULL;
		rank=0;
		linkNodes=NULL;
	}
	int nodeID;
	Node* parent;
	int rank;
	LinkNode* linkNodes;
	bool AddLinkNode(Edge edge);
};

bool Node::AddLinkNode(Edge edge)
{
	int linkID=-1;
	if(edge.nId1==nodeID)
	{
		linkID=edge.nId2;
	}
	else
	{
		linkID=edge.nId1;
	}

	if(linkNodes==NULL)
	{
		linkNodes=new LinkNode();
		linkNodes->length=edge.length;
		linkNodes->nodeID=linkID;
		return true;
	}
	else
	{
		LinkNode* tLinkNode=linkNodes;
		while(tLinkNode->nextNode!=NULL && tLinkNode->nodeID!=linkID)
		{
			tLinkNode=tLinkNode->nextNode;
		}
		if(tLinkNode->nextNode==NULL)
		{
			LinkNode* newLinkNode=new LinkNode();
			newLinkNode->length=edge.length;
			newLinkNode->nodeID=linkID;
			tLinkNode->nextNode=newLinkNode;
			return true;
		}
		else 
		{
			if(tLinkNode->length>edge.length)
			{
				tLinkNode->length=edge.length;
				return true;
			}
		}
	}
	return false;
}

class Graph
{
public:
	vector<Node> nodeVec;
	vector<Edge> edgeVec;
	int iNodeNum;
	int iEdgeNum;
	bool InsertEdge(Edge edge);
};

bool Graph::InsertEdge(Edge edge)
{
	if(nodeVec[edge.nId1].AddLinkNode(edge) && nodeVec[edge.nId2].AddLinkNode(edge))
	{
		edgeVec.push_back(edge);
		return true;
	}
	
	return false;
}


bool SortEdge(Edge e1,Edge e2)
{
	return e1.length<e2.length;
}

void MakeSet(Node& x)
{
	x.parent=&x;
	x.rank=0;
}

Node* FindSet(Node* node)
{
	if(node->parent != node)
	{
		node->parent=FindSet(node->parent);
	}
	return node->parent;
}


void LinkTwoTree(Node* pNode1,Node* pNode2)
{
	if(pNode1->rank>pNode2->rank)
	{
		pNode2->parent=pNode1;
	}
	else if(pNode1->rank<pNode2->rank)
	{
		pNode1->parent=pNode2;
	}
	else
	{
		pNode1->parent=pNode2;
		pNode2->rank++;
	}
}

void UnionSets(Node* pNode1,Node* pNode2)
{
	LinkTwoTree(FindSet(pNode1),FindSet(pNode2));
}


vector<Edge>* MinSpanTree_Kruscal(Graph graph)
{
	vector<Edge> *mSpanTree=new vector<Edge>();
	for(vector<Node>::iterator nodeIter=graph.nodeVec.begin();nodeIter!=graph.nodeVec.end();nodeIter++)
	{
		MakeSet(*nodeIter);
	}

	sort(graph.edgeVec.begin(),graph.edgeVec.end(),SortEdge);
	int iUnionNumber=0;
	for(vector<Edge>::iterator edgeIter=graph.edgeVec.begin();edgeIter!=graph.edgeVec.end();edgeIter++ )
	{
		if(FindSet( &graph.nodeVec[edgeIter->nId1-1] ) != FindSet(&graph.nodeVec[edgeIter->nId2-1]))
		{
			UnionSets(&graph.nodeVec[edgeIter->nId1-1],&graph.nodeVec[edgeIter->nId2-1]);
			mSpanTree->push_back(*edgeIter);
		}
	}
	return mSpanTree;
}

int main()
{
	Graph graph;
	int ai,bi,len;
	int n,m;
	cin>>n>>m;
	graph.iNodeNum=n;
	graph.iEdgeNum=m;

	for(int i=0;i<n;i++)
	{
		graph.nodeVec.push_back(Node());
	}

	for(int i=0;i<m;i++)
	{
		cin>>ai>>bi>>len;
		Edge edge;
		edge.nId1=ai;
		edge.nId2=bi;
		edge.length=len;
		graph.edgeVec.push_back(edge);
	}

	
	vector<Edge>mSpanTree=*MinSpanTree_Kruscal(graph);
	cout<<mSpanTree[mSpanTree.size()-1].length<<endl;
	return 0;

}