#include <iostream>
#include <lemon/list_graph.h>
#include <lemon/matching.h>
#include <lemon/adaptors.h>

int main() {
  typedef lemon::ListDigraph Graph;
  Graph g;
  lemon::ListDigraph::ArcMap<float> arc_cost(g);


  lemon::ListDigraph::Node n1 = g.addNode();
  lemon::ListDigraph::Node n2 = g.addNode();
  lemon::ListDigraph::Node n3 = g.addNode();
  lemon::ListDigraph::Node n4 = g.addNode();
  
  arc_cost[g.addArc(n1, n3)] = 10;
  arc_cost[g.addArc(n1, n4)] = 20;
  arc_cost[g.addArc(n2, n3)] = 35;
  arc_cost[g.addArc(n2, n4)] = 40;

  lemon::Undirector<lemon::ListDigraph> undirectedGraph(g);
  lemon::MaxWeightedMatching<lemon::Undirector<lemon::ListDigraph>,lemon::ListDigraph::ArcMap<float> > matching(undirectedGraph,arc_cost);
  
  matching.run();
  
  std::cout << matching.matchingWeight() << std::endl;  

  return 0;
}