Problem 1280 : Slim Span

Problem F: Slim Span
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1280

• 問題概要

エッジのコストの最小値と最大値の差が一番ちいさくなるような全域木をつくったとき、その差をもとめよ。

• 解法

エッジの数だけ最小全域木をつくる。
そのエッジを最小のコストのエッジとして、それよりおおきなエッジだけみて構築してコストをだして最小のものをだす。

プリムでもできるだろうけど、せっかくなのでクラスカルを実装してみた。
ディスジョイントセットの経路圧縮に手間取ったけど、うまいことかけた。

• ソース

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<sstream>
#include<cassert>
#include<queue>
#include<stack>

#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n)   REP(i,0,n)
#define ALL(C)     (C).begin(),(C).end()
#define FOR(it,o)  for(__typeof((o).begin()) it=(o).begin(); it!=(o).end(); ++it)

using namespace std;

class Node{
public:
  Node *p;
  Node(){
    p = this;
  }
  Node *find(){
    if(p != p-> p){
      p = (*p).find();
    }
    return p;
  }
};

class Edge{
public:
  int n1, n2, cost;
  bool operator < (const Edge e)const{
    return cost < e.cost;
  }
};

const int INF = 1000000000;

int MST(int id, vector<Edge> &E, int node){
  Node n[node];
  int  maxi = 0;
  REP(i, id, E.size()){
    n[E[i].n1].find();
    n[E[i].n2].find();
    if(n[E[i].n1].p != n[E[i].n2].p){
      n[E[i].n1].p->p = n[E[i].n2].p;
      maxi = max(maxi, E[i].cost - E[id].cost);
    }
  }
  rep(i, node-1){
    n[i].find();
    n[i+1].find();;
    if(n[i].p != n[i+1].p)return INF;
  }
  return maxi;
}


main(){
  int n, m;
  while(cin >> n >> m){
    if(n + m == 0)break;
    vector<Edge> E;
    rep(i, m){
      Edge e;
      cin >> e.n1 >> e.n2 >> e.cost;
      e.n1--;
      e.n2--;
      E.push_back(e);
    }
    sort(ALL(E));
    int ans = INF;
    rep(i, m){
      ans = min(ans, MST(i, E, n));
    }
    if(ans == INF)cout << -1 << endl;
    else cout << ans << endl;
  }
}