POJ 3925 - Minimal Ratio Tree

http://poj.org/problem?id=3925

概要

すべてのノードとエッジに重みがある木に対して，ratio を

Ratio := Σedge_weight / Σnode_weight

と定める．

与えられた n 個のノードからなる重み付きグラフのサブグラフのうち，m 個のノードからなる ratio が最小の木を答える．

制約

解法

m 個のノードの選び方は全探索．

すると Σnodeweight が決まるので，Ratio を小さくするには Σedgeweight を小さくすればよい． これは最小全域木を求めればいい．

  1 #include <iostream>
  2 #include <vector>
  3 #include <algorithm>
  4 #include <iterator>
  5 using namespace std;
  6 
  7 class DisjointSet/*{{{*/
  8 {
  9   private:
 10     vector<int> parent;
 11 
 12     int root(int x)
 13     {
 14       if (parent[x] < 0) {
 15         return x;
 16       } else {
 17         parent[x] = root(parent[x]);
 18         return parent[x];
 19       }
 20     }
 21 
 22   public:
 23     explicit DisjointSet(int n) : parent(n, -1) {}
 24 
 25     bool unite(int x, int y)
 26     {
 27       const int a = root(x);
 28       const int b = root(y);
 29       if (a != b) {
 30         if (parent[a] < parent[b]) {
 31           parent[a] += parent[b];
 32           parent[b] = a;
 33         } else {
 34           parent[b] += parent[a];
 35           parent[a] = b;
 36         }
 37         return true;
 38       } else {
 39         return false;
 40       }
 41     }
 42 
 43     bool find(int x, int y) { return root(x) == root(y); }
 44     int size(int x) { return -parent[root(x)]; }
 45 };/*}}}*/
 46 
 47 struct edge {/*{{{*/
 48   int u, v;
 49   typedef int weight_type;
 50   weight_type w;
 51   edge(int s, int d, weight_type w_) : u(s), v(d), w(w_) {}
 52   bool operator<(const edge& that) const { return w < that.w; }
 53 };/*}}}*/
 54 
 55 int main()
 56 {
 57   int n, m;
 58   while (cin >> n >> m && n != 0) {
 59     vector<int> weights(n);
 60     for (int i = 0; i < n; i++) {
 61       cin >> weights[i];
 62     }
 63     vector<edge> edges;
 64     for (int i = 0; i < n; i++) {
 65       for (int j = 0; j < n; j++) {
 66         int w;
 67         cin >> w;
 68         if (i < j) {
 69           edges.push_back(edge(i, j, w));
 70         }
 71       }
 72     }
 73     sort(edges.begin(), edges.end());
 74 
 75     vector<bool> use(n, false);
 76     for (int i = 0; i < m; i++) {
 77       use[i] = true;
 78     }
 79     sort(use.begin(), use.end());
 80     int min_ew = 0, min_nw = 0;
 81     vector<int> ans;
 82     do {
 83       int nw = 0;
 84       vector<int> nodes;
 85       for (int i = 0; i < n; i++) {
 86         if (use[i]) {
 87           nw += weights[i];
 88           nodes.push_back(i+1);
 89         }
 90       }
 91 
 92       // kruskal
 93       DisjointSet s(n);
 94       int ew = 0;
 95       for (vector<edge>::const_iterator it(edges.begin()); it != edges.end(); ++it) {
 96         if (use[it->u] && use[it->v] && s.unite(it->u, it->v)) {
 97           ew += it->w;
 98           if (s.size(it->u) == m) {
 99             if (min_nw == 0 || ew*min_nw <= min_ew*nw) {
100               min_ew = ew;
101               min_nw = nw;
102               ans = nodes;
103             }
104             break;
105           }
106         }
107       }
108     } while (next_permutation(use.begin(), use.end()));
109     copy(ans.begin(), ans.end(), ostream_iterator<int>(cout, " "));
110     cout << endl;
111   }
112   return 0;
113 }
poj/3925.cc