live archive 5015 Spread Out Message

Spread Out Message
http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=390&page=show_problem&problem=3016

問題概要

無効グラフのすべてのノードのペアに対してのエッジの重みが与えられるので、
エッジがn-1本でかつ、エッジの重みの合計を最大化せよ。

解法

最大全域木を作る。
クラスカルで重みが大きいものから繋げていった。

ソース

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<cmath>

#define REP(i, b, n) for(int i = b; i <(int)n; i++)
#define rep(i, n) REP(i, 0, n)

using namespace std;

class DisJointSet{
public:
  vector<int> v;
  DisJointSet(int n){
    v = vector<int>(n);
    rep(i, n)v[i] = i;
  }
  int find(int x){
    if(v[x] == x)return x;
    else return v[x] = find(v[x]);
  }
  void unite(int x, int y){
    x = find(x);
    y = find(y);
    if(x == y)return;
    v[x] = y;
  }
  bool same(int x, int y){
    return find(x) == find(y);
  }
};

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

int MST(vector<Edge> &E, int &node){
  sort(E.begin(), E.end());
  DisJointSet n(node);
  int cost = 0;
  rep(i, E.size()){
    int from = E[i].n1, to = E[i].n2;
    if(n.same(from, to))continue;
    cost += E[i].cost;
    n.unite(from, to);
  }
  return cost;
}
int main(){
  int n;
  while(cin >> n){
    if(n == 0)break;
    vector<Edge> E;
    rep(i, n){
      rep(j, n){
	int tmp;
	cin >> tmp;
	E.push_back((Edge){i, j, tmp});
      }
    }
    cout << MST(E, n) << endl;
  }
}