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; } }