Poj 2395: Out of Hay

poj2395.md

Poj 2395: Out of Hay

題目

分析

求 MST 裡的最長邊，水題，Kruskal 是你的好朋友

AC Code

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;

struct Edge {
	int u, v, cost;
	bool operator < (const Edge& e) const {
		return cost < e.cost;
	}
};

int N, M;
Edge edges[10000];

int parent[2000];
int height[2000];

void init() {
	for (int i = 0; i < N; i++) {
		parent[i] = i;
		height[i] = 0;
	}
}
int find(int a) {
	if (parent[a] == a)
		return a;
	return parent[a] = find(parent[a]);
}
void unite(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b) return;
	
	if (height[a] < height[b])
		parent[a] = b;
	else {
		parent[b] = a;
		if (height[a] == height[b])
			height[a]++;
	}
}
bool same(int a, int b) {
	return find(a) == find(b);
}

int solve() {
	sort(edges, edges + M);
	
	init();
	
	int longest = -1;
	
	for (int i = 0; i < M; i++) {
		Edge& e = edges[i];
		if (!same(e.u, e.v)) {
			unite(e.u, e.v);
			if (e.cost > longest) 
				longest = e.cost;
		}
	}
	
	return longest;
}


int main() {
	scanf("%d %d", &N, &M);
	for (int i = 0; i < M; i++) {
		int a, b, w;
		scanf("%d %d %d", &a, &b, &w);
		edges[i] = Edge{a, b, w};
	}
	
	printf("%d\n", solve());
	
	return 0;
}