网易笔试8.8（生成树最大权值与最小权值之差最小）

#include <bits/stdc++.h>

using namespace std;

struct Edge{
	int u, v;
	int w;
};

bool inSameSet(int *uni, int r1, int r2) {
	while(r1 != uni[r1]) r1 = uni[r1];
	while(r2 != uni[r2]) r2 = uni[r2];
	
	if(r1 == r2) return true;
	uni[r1] = r2;
	return false;
}

int solution() {
	int n, m;
	cin >> n >> m;
	
	//顶点为1时，边数自然为0 
	if(n == 1) 
		return 0;	
	
	int uni[n+1];
	for(int i = 1; i<=n; ++i) uni[i] = i;
	
	Edge edge[m];
	for(int i = 0; i<m; ++i) {
		cin >> edge[i].u >> edge[i].v >> edge[i].w; 
	}
	
	sort(edge, edge+m, [](Edge& a, Edge& b) {
		return a.w < b.w;
	});
	
	int l, r, dw = n-2, min_d = INT_MAX;
	for(int i = dw; i<m; ++i) {
		if(edge[i].w - edge[i-dw].w < min_d) {
			r = i;
			min_d = edge[i].w - edge[i-dw].w;
		}
	}
	
	l = r-dw;
	
	//先加l, l+1, ..., r这n-1条边，看是否构成树
	int cnt = 0;	//加入的边数 
	for(int i = l; i<=r; ++i) {
		if(!inSameSet(uni, edge[i].u, edge[i].v)) {
			++cnt;
		}
	}	
	
	//若边数cnt小于n-1则还得往两边去找边加入到集合中，直到找到n-1条边 
	while(l >= 0 && r<n && cnt < n-1) {
		if(l == 0) {
			++r;
			if(r<n && !inSameSet(uni, edge[r].u, edge[r].v)) {
				++cnt;
			}
		} else if(r == n-1) {
			--l;
			if(l>=0 && !inSameSet(uni, edge[l].u, edge[l].v)) {
				++cnt;
			}
		} else {
			
			if(edge[r].w - edge[l-1].w < edge[r+1].w -edge[l].w) {
				--l;
				if(!inSameSet(uni, edge[l].u, edge[l].v)) ++cnt;
			} else{
				++r;
				if(!inSameSet(uni, edge[r].u, edge[r].v)) ++cnt;
			}
		}
	}
	
	return edge[r].w - edge[l].w;
}

int main()
{
	cout << solution() << endl;
	return 0;
 }