lemon graph library を使う

インストール

tar で固まって置いてある 1.2.3 は結構古いっぽく，ドキュメントに出てくるアルゴリズムがたまに無いっぽい（例えば Nagamochi-Ibaraki が無かった）．

hg clone http://lemon.cs.elte.hu/hg/lemon-main

サイトには Linux では autoreconf しろと書いてあるが，「configure.ac も configure.in も無いよう＞＜」と言われて動かない．CMakeLists.txt が置いてあるので，cmake してみたらインストールできたっぽい．

cmake ./
make
sudo make install

使う

ハマった点：無向グラフでは ArcMap ではなく EdgeMap を使うっぽい．

#include <map>
#include <cstdio>
#include <lemon/list_graph.h>
#include <lemon/hao_orlin.h>
#include <lemon/nagamochi_ibaraki.h>

using namespace lemon;
using namespace std;

#define all(c) (c).begin(), (c).end()
#define iter(c) __typeof((c).begin())
#define cpresent(c, e) (find(all(c), (e)) != (c).end())
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define tr(c, i) for (iter(c) i = (c).begin(); i != (c).end(); ++i)
#define pb(e) push_back(e)
#define mp(a, b) make_pair(a, b)

int main() {
  ListGraph g;
  ListGraph::EdgeMap<int> w(g);

  vector<pair<int, int> > es;
  int V = 0;
  for (int u, v; 2 == scanf("%d%d", &u, &v); ) {
    if (u > v) swap(u, v);
    es.pb(mp(u, v));
    V = max(V, max(u, v) + 1);
  }

  vector<ListGraph::Node> vs(V);
  rep (v, V) vs[v] = g.addNode();
  rep (i, es.size()) {
    ListGraph::Edge e = g.addEdge(vs[es[i].first], vs[es[i].second]);
    w[e] = 1;
  }

  NagamochiIbaraki<ListGraph> nagamochi_ibaraki(g, w);
  nagamochi_ibaraki.run();
  printf("%d\n", nagamochi_ibaraki.minCutValue());

  return 0;
}