週刊 spaghetti_source

追記

17:42

追記（2012/12/01）：みつかりました．k = 2，n ≦ 8 に対しては，全探索で動作確認していますが，自信はありません．

#define REP(i,n) for(int i=0;i<n;++i)
#define FOR(i,c) for(__typeof(c.begin())i=c.begin();i!=c.end();++i)
#define ALL(c) (c).begin(),(c).end()

struct UnionFind {
  vector<int> data;
  UnionFind(int size) : data(size, -1) { }
  bool unite(int x, int y) {
    x = root(x); y = root(y);
    if (x != y) {
      if (data[y] < data[x]) swap(x, y);
      data[x] += data[y]; data[y] = x;
    }
    return x != y;
  }
  bool find(int x, int y) { return root(x) == root(y); }
  int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); }
  int size(int x) { return -data[root(x)]; }
};

struct Graph {
  int n, m;
  struct Edge {
    int s, t;
    int c;
    Edge(int s, int t, int c) : s(s), t(t), c(c) { };

    int id; // e in F_{e->id}
    Edge *prev; // e is an alternative for e->prev
  } NIL;
  vector<Edge> edge;
  void addEdge(int s, int t, int c) {
    edge.push_back(Edge(s, t, c));
  }
  Graph(int n) : n(n), m(0), NIL(-1,-1,0) { NIL.prev = &NIL; }
  typedef vector< set<Edge*> > Forest; // complexity increased by log n factor
  vector<Forest> forest;

  // pick connected component which contains x, and orient edges to x
  void orientTree(int u, Forest &F, vector<Edge *> &p) {
    FOR(i, F[u]) {
      Edge *e = (*i);
      if (e == p[u]) continue;
      if (e->s == u) swap(e->s, e->t);
      e->prev = 0; 
      p[e->s] = e;
      orientTree(e->s, F, p);
    }
  }
  bool augment(Edge *e0, int k) {
    int x = e0->s, y = e0->t;
    vector< vector<Edge *> > parent(k, vector<Edge*>(n));
    REP(i, k) { 
      parent[i][x] = &NIL;
      orientTree(x, forest[i], parent[i]);
    }
    queue<Edge*> Q; Q.push(e0);
    while (!Q.empty()) { // find augment path 
      Edge *e = Q.front(); Q.pop();
      int u = e->s, v = e->t, j = (e->id+1) % k;
      if (!parent[j][u] || !parent[j][v]) { // e can be added to F_j
        forest[j][u].insert(e);
        forest[j][v].insert(e);
        e->id = j;
        for (Edge *f; f = e->prev; e = f) { 
          f->id = (e->id+k-1)%k;
          forest[f->id][e->s].erase(e);
          forest[f->id][e->t].erase(e);
          forest[f->id][f->s].insert(f);
          forest[f->id][f->t].insert(f);
        }
        return true;
      } else { // e makes cycle -> enqueue circuit edges
        if (parent[j][u]->prev) swap(u, v);
        stack<Edge *> S; // near x edges first
        for (; !parent[j][u]->prev; u = parent[j][u]->t) S.push(parent[j][u]);
        for (; !S.empty(); S.pop()) { S.top()->prev = e; Q.push(S.top()); }
      }
    }
    return false;
  }
  static bool Compare(Edge i, Edge j) { return i.c > j.c; }
  int disjointForest(int k) {
    FOR(i, edge) { i->id = -1; i->prev = 0; }
    sort(ALL(edge), Compare);
    forest = vector<Forest>(k, Forest(n));
    int cost = 0;
    UnionFind clump(n); // clumps form disjoint sets
    FOR(i, edge) { 
      Edge &e = *i;
      if (clump.find(i->s, i->t)) continue;
      if (augment(&(*i), k)) cost += i->c;
      else clump.unite(i->s, i->t);
    }
    return cost;
  }
};