AOJ 2536 Median Tree

問題

Median Tree | Aizu Online Judge

問題概要

無向連結グラフが与えられる。各エッジにはコストが付いているので、そのコストの中央値が最小となるような全域木を求めよ。

解法

採用するエッジの数はN-1本。そのうち、コストが小さいものから順にk+1本、k本と分ける(k+1+k == N-1)。前半のk+1本はできるだけコストが小さいものの方がよく、後半のk本はコストがどのようなものでも全域木が作れれば良い。このことから、クラスカル法で普通に最小全域木を求めれば最小の中央値も求まる。

コード

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
#include <queue>
#include <complex>
  
#define INF 100000000
#define YJ 1145141919
#define INF_INT_MAX 2147483647
#define INF_LL_MAX 9223372036854775807
#define INF_LL 9223372036854775
#define EPS 1e-10
#define Pi acos(-1)
#define LL long long
#define ULL unsigned long long
#define LD long double 

using namespace std;

#define MAX_N 1005
#define MAX_M 10005

int N, M;

class classEdge{
public:
  int from, to, cost;
  classEdge(int from = 0, int to = 0, int cost = 0) : from(from), to(to), cost(cost){}

  bool operator < (const classEdge& p) const{
    return cost < p.cost;
  }

}Edge[MAX_M];

bool input(){
  
  cin >> N >> M;
  if((N | M) == 0)
    return false;

  for(int i = 0; i < M; i++){
    int f, t, c;
    cin >> f >> t >> c;
    Edge[i] = classEdge(f, t, c);
  }

  return true;

}

class classUnionFind{
public:
  classUnionFind(){
    init();
  }

  void init(){
    for(int i = 0; i < MAX_N; i++){
      par[i] = i;
    }
  }

  int find(int x){
    if(x == par[x])
      return x;
    else
      return par[x] = find(par[x]);
  }

  void unite(int x, int y){
    x = find(x);
    y = find(y);
    if(x == y)
      return;
    par[x] = y;
  }

  bool same(int x, int y){
    return find(x) == find(y);
  }

private:
  int par[MAX_N];
}UnionFind;

int solve(){

  UnionFind.init();
  
  sort(Edge, Edge+M);

  int n = 0;
  for(int i = 0; i < M; i++){
    
    classEdge edge = Edge[i];

    if(UnionFind.same(edge.from, edge.to))
      continue;

    UnionFind.unite(edge.from, edge.to);
    n++;
    //この時点で中央値が確定する
    if(n == (N-1)/2+1)
      return edge.cost;

  }

  //グラフは連結なので、この行が実行されることはない
  return -1;

}

int main(){

  while(input()){
    cout << solve() << endl;
  }

  return 0;

}