Hatena::Grouptopcoder

cou929のTopCoder日記

2009-12-15

SRM386 div2 (過去問)

23:21

Hard - LittleTree

グラフの高さを height 以下にするときの, 最小コストを求める問題.

集中力が切れてしまったので途中で一旦やめました. 一応考えたのはgreedyな方法で, ルートから下へ探索していき, height以上になった際にそのノードをaugmentするというものです. 当然ですがテストケース0など, height以下のノードをaugmentした方が最適なケースもあるので, うまくいきません.

class LittleTree {
public:
  int toInt(string s) {int r = 0; istringstream ss(s); ss >> r; return r;}

  vector <string> split(const string _s, const string del) {
    vector <string> ret;
    string s = _s;

    while (!s.empty())
      {
        size_t pos = s.find(del);
        string sub = "";
        sub = s.substr(0, pos);
        ret.push_back(sub);
        if (pos != string::npos)
          pos += del.size();
        s.erase(0, pos);
      }

    return ret;
  }

  int minCost(int N, vector <string> e, int height) {
    int ret = 0;
    string edge_string;
    int graph[100][100];
    bool fixed[100];
    memset(graph, 0, sizeof(graph));
    memset(fixed, false, sizeof(fixed));

    for (int i=0; i<e.size(); i++)
      edge_string += e[i];

    vector <string> tmp = split(edge_string, " ");
    for (int i=0; i<tmp.size(); i++) {
      vector <string> t = split(tmp[i], ",");
      graph[toInt(t[0])][toInt(t[1])] = 1;
    }

    queue <pair <int, int> > q;
    q.push(make_pair(0, 0));
    fixed[0] = true;

   
    while (!q.empty()) {
      pair <int, int> cur = q.front();
      q.pop();

      int cur_node = cur.first;
      int cur_level = cur.second;

      if (cur_level > height) {
        int parent = 0;
        int grandparent = 0;
        for (int i=0; i<100; i++)
          if (graph[i][cur_node] == 1) {
            parent = i;
            break;
          }
        for (int i=0; i<100; i++)
          if (graph[i][parent] == 1) {
            grandparent = i;
            break;
          }

        graph[parent][cur_node] = 0;
        graph[grandparent][cur_node] = 1;
        ret++;
        q.push(make_pair(cur_node, cur_level-1));
      } else {
        for (int i=0; i<100; i++)
          if (graph[cur_node][i] == 1 && !fixed[i])
            q.push(make_pair(i, cur_level+1));
        fixed[cur_node] = true;
      }
    }

    return ret;
  }
};