Această problemă cere pentru un graf cu $N (N<=100)$ noduri să aflăm diferenţa minimă dintre muchia de cost maxim şi cea de cost minim dintr-un arbore de acoperire al grafului.

Dimensiunea datelor de intrare ne permite ca pentru fiecare muchie să alegem doar muchii de cost mai mare până când obţinem un arbore de acoperire şi să alegem cea mai bună diferenţă dintre toţi arborii de acoperire obţinuţi.

Sursa
 
==code(cpp)|
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#define x first
#define y second
#define DN 105
using namespace std;
 
int n,m,pre[DN];
vector<pair<int,pair<int,int> > > mc;
 
int find(int x) {
	if(pre[x]==x) return x;
	pre[x]=find(pre[x]);
	return pre[x];
}
 
void unite(int x,int y) {
	pre[find(x)]=find(y);
}
 
int main() {
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	for(;;) {
		cin>>n>>m;
		if(!n && !m) break;
 
		for(int i=0; i<m; ++i) {
			int a,b,c;
			cin>>a>>b>>c;
			mc.push_back(make_pair(c,make_pair(a,b)));
		}
		sort(mc.begin(),mc.end());
		int rez=(1<<30);
		for(int fm=0; fm<mc.size(); ++fm) {
//Alegem muchia care să aibă costul cel mai mic din apm
			int nrm=0,mx;
			for(int i=1; i<=n; ++i) pre[i]=i;
			for(int i=fm; i<mc.size(); ++i) if(find(mc[i].y.x)!=find(mc[i].y.y)) {
				unite(mc[i].y.x,mc[i].y.y);
				mx=mc[i].x;
				++nrm;
			}
			if(nrm==n-1) rez=min(rez,mx-mc[fm].x);
		}
		if(rez!=(1<<30)) cout<<rez<<'\n';
		else cout<<"-1\n";
		mc.clear();
	}
}
==