#include <cstdlib>
#include <iostream>
#include <sstream>

#include <lemon/smart_graph.h>

#include <lemon/bpugraph_adaptor.h>
#include <lemon/bipartite_matching.h>

#include <lemon/graph_utils.h>
#include <lemon/xy.h>
#include <lemon/graph_to_eps.h>

#include <lemon/time_measure.h>

using namespace std;
using namespace lemon;

typedef SmartBpUGraph Graph;
BPUGRAPH_TYPEDEFS(Graph);

int _urandom_init() {
  int seed = time(0);
  srand(seed);
  return seed;
}

int urandom(int n) {
  static int seed = _urandom_init();
  ignore_unused_variable_warning(seed);
  return (int)(rand() / (1.0 + RAND_MAX) * n);
}

int main() {

  for (int k = 1; k < 100; ++k) {
    
    int n = k * 100;
    int m = (100 - k) * 100;
    int e = 20000;
    int s = 100;
    
    Timer nt(false), st(false);
    
    for (int i = 0; i < s; ++i) {
      Graph graph;
      vector<Node> aNodes;
      vector<Node> bNodes;  
      
      for (int i = 0; i < n; ++i) {
        Node node = graph.addANode();
        aNodes.push_back(node);
      }
      for (int i = 0; i < m; ++i) {
        Node node = graph.addBNode();
        bNodes.push_back(node);
      }
      for (int i = 0; i < e; ++i) {
        Node aNode = aNodes[urandom(n)];
        Node bNode = bNodes[urandom(m)];
        graph.addEdge(aNode, bNode);
      }

      {
        MaxBipartiteMatching<Graph> bpmatch(graph);
        
        nt.start();
        bpmatch.init();
        bpmatch.start();
        nt.stop();
        
      }

      {
        typedef SwapBpUGraphAdaptor<Graph> SGraph;
        SGraph sgraph(graph);
        MaxBipartiteMatching<SGraph> bpmatch(sgraph);

        st.start();
        bpmatch.init();
        bpmatch.start();
        st.stop();
        
      }
                  
    }

    cout << k * 100 << ' ' << nt.realTime() << ' ' << st.realTime() << endl;

  }

  return 0;
}