bzoj1083: [SCOI2005]繁忙的都市

第一问n-1无疑

第二问最小生成树kruskal（不知道有没有算错）算法的改进版

const int N = 310, M = 90010;
struct Edge {
	int u, v, Val;
	inline bool operator <(const Edge &B) const { return Val < B.Val; }
	//friend bool operator <(const Edge &A, const Edge &B) { return A.Val < B.Val; }
} E[M];
int n, m;
int Fa[N];

inline void Input() {
	scanf("%d%d", &n, &m);
	Rep(i, m) scanf("%d%d%d", &E[i].u, &E[i].v, &E[i].Val);
}

inline int Find(int x) { return x == Fa[x] ? x : Fa[x] = Find(Fa[x]); }
inline void Solve() {
	sort(E, E + m);
	For(i, 1, n) Fa[i] = i;
	int Ans = 0;
	Rep(i, m) {
		int u = Find(E[i].u), v = Find(E[i].v);
		if(u ^ v) Fa[u] = v, Ans = max(Ans, E[i].Val);
	}
	printf("%d %d\n", n - 1, Ans);
}

int main() {
	#ifndef ONLINE_JUDGE
	SETIO("1083");
	#endif
	Input();
	Solve();
	return 0;
}