POJ 1861 Network

題意&想法：
     要找出最小生成樹MST，先輸出MST最長的邊長，再輸出MST有幾條邊(就是N-1)，然後在一一輸出這些邊的點。用Kruskal演算法找出MST，並依題輸出答案。
    ps.這題Sample Output有誤，4個點只需要3條邊就可以產生MST。

	#include <cstdio>
	#include <vector>
	#include <algorithm>
	using namespace std;
	struct Edge{
	int A;
	int B;
	int Len;
	}E[15001];
	int Set[1001];
	bool cmp(const Edge &A, const Edge &B);
	void Set_Initial(const int &N);
	int Find_Root(const int &x);
	bool Union(const Edge &E);
	int main()
	{
	int N, M, A, B, L;
	while (scanf("%d %d", &N, &M) == 2) {
	for (int i = 0; i < M; ++i)
	scanf("%d %d %d", &E[i].A, &E[i].B, &E[i].Len);
	sort(E, E + M, cmp);
	Set_Initial(N);
	vector<Edge> Ans;
	for (int i = 0, currentEdge = 0; currentEdge != N - 1; ++i)
	if (Union(E[i])){
	++currentEdge;
	Ans.push_back(E[i]);
	}
	printf("%d\n", (Ans.end()-1)->Len);
	printf("%d\n", Ans.size());
	for (int i = 0; i < Ans.size(); ++i)
	printf("%d %d\n", Ans[i].A, Ans[i].B);
	}
	}
	bool cmp(const Edge &A, const Edge &B) {
	return A.Len < B.Len;
	}
	void Set_Initial(const int &N)
	{
	for (int i = 1; i <= N; ++i)
	Set[i] = i;
	}
	int Find_Root(const int &x)
	{
	if (x == Set[x])
	return x;
	return Set[x] = Find_Root(Set[x]);
	}
	bool Union(const Edge &E)
	{
	int x = Find_Root(E.A);
	int y = Find_Root(E.B);
	if (x != y) {
	Set[x] = y;
	return true;
	}
	return false;
	}

view raw [POJ] 1861 Network.cpp hosted with ❤ by GitHub