AOJ : 1280 - Slim Span

問題概要

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1280
全域木の最大エッジコストと最小エッジコストの差が最小になるように, ノード数n, エッジ数n-1, となる全域木を作ったとき, その最大と最小の差はいくらか.
もし, このような木が作れない場合は, -1 を出力.

アルゴリズム

クラスカル法で解きました.
まず, エッジをコストの昇順に並べておきます.
そして, 最初に使うエッジを決定して, このエッジからコストが小さい順に全域木に追加していきます.
全域木が完成した時点で, そのときの最大エッジと最小エッジの差をとり, 答えを更新します.

Union-Findのソースは, ICPCチャレンジブックから引用してるので省略.

プログラム

#define INF 999999999

class E{
public:
  int from,to,cost;
  E(int _from,int _to,int _cost){省略}
  bool operator<(const E &e)const{省略}
};

int n,m;
vector<E> es;

int par[102];
int rank[102];

void init(void){省略}
int find(int x){省略}
void unite(int x,int y){省略}
bool same(int x,int y){省略}

int kruskal(void){
  init();
  int last = -1;
  int cnt = 0;

  rep(i,es.size()){
    E e = es[i];

    if(!same(e.from,e.to)){
      unite(e.from,e.to);
      last = i;
      cnt++;
    }
  }
  return cnt!=n-1 ? INF : es[last].cost - es[0].cost;
}

int main(void){
  while(cin>>n>>m,n){
    es.clear();
    rep(i,m){
      int a,b,cost;
      cin>>a>>b>>cost;
      es.push_back(E(a,b,cost));
    }

    int ans = INF;
    sort(es.begin(),es.end());
    while(es.size() >= n-1){
      int res = kruskal();
      if(res == INF) break;
      if(ans > res) ans = res;
      es.erase(es.begin());
    }

    cout<<(ans==INF ? -1 : ans)<<endl;
  }

  return 0;
}