Problem: Example

Input

3
0 1
0 0 0 1
0 1 0 2
0 2 0 3


Output

6.0000000000000000

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
#define f first
#define s second
#define mp make_pair
#define pi M_PI
#define inf 1<<30
#define eps (1e-11)
#define MAX 700
#define equals(a,b) (fabs((a)-(b))<eps)
using namespace std;

class Point{
public:
  double x,y;
  Point(double x=0,double y=0):x(x),y(y){}

  Point operator+(Point p){ return Point(x+p.x,y+p.y);}
  Point operator-(Point p){ return Point(x-p.x,y-p.y);}
  Point operator*(double k){ return Point(x*k,y*k);}
  Point operator/(double k){ return Point(x/k,y/k);}
  bool operator<(Point p)const{ return (x!=p.x ? x<p.x : y<p.y);}
  bool operator==(Point p)const{ return fabs(x-p.x)<eps && fabs(y-p.y)<eps;}

  double abs(){ return sqrt(norm());}
  double norm(){ return (x*x+y*y);}
};
typedef Point Vector;
typedef vector<Point> Polygon;

class Segment{
public:
  Point p1,p2;
  Segment(Point p1=Point(),Point p2=Point()):p1(p1),p2(p2){}
};
typedef Segment Line;

double norm(Vector a){ return (a.x*a.x+a.y*a.y);}
double abs(Vector a){ return sqrt(norm(a));}
double dot(Vector a,Vector b){ return (a.x*b.x+a.y*b.y);}
double cross(Vector a,Vector b){ return (a.x*b.y-a.y*b.x);}

struct edge{ 
  int to,cap;
  double cost;
  int rev;
};

int v;
vector<edge> e[MAX];
double h[MAX];
double dist[MAX];
int prevv[MAX],preve[MAX];

void add_edge(int from,int to,int cap,double cost){
  e[from].push_back((edge){to,cap,cost,(int)e[to].size()});
  e[to].push_back((edge){from,0,-cost,(int)e[from].size()-1});
}

typedef pair<int,double> P;

double min_cost_flow(int s,int t,int f){
  double res=0.0;
  fill(h,h+v,0);
  while(f>0){
    priority_queue<P,vector<P>,greater<P> > pq;
    fill(dist,dist+v,inf);
    dist[s]=0;
    pq.push(P(0,s));
    while(pq.size()){
      P p=pq.top();
      pq.pop();
      int u=p.second;
      if(dist[u]-p.first<-eps)continue;
      for(int i=0;i<e[u].size();i++){
        edge &E=e[u][i];
        if(E.cap>0 && (dist[u]+E.cost+h[u]-h[E.to])-dist[E.to]<-eps){
          dist[E.to]=dist[u]+E.cost+h[u]-h[E.to];
          prevv[E.to]=u;
          preve[E.to]=i;
          pq.push(P(dist[E.to],E.to));
        }
      }
    }
    if(dist[t]==inf)return -1;
    for(int i=0;i<v;i++)h[i]+=dist[i];

    int d=f;
    for(int u=t;u!=s;u=prevv[u]){
      d=min(d,e[prevv[u]][preve[u]].cap);
    }
    f-=d;
    res+=(double)d*h[t];
    for(int u=t;u!=s;u=prevv[u]){
      edge &E=e[prevv[u]][preve[u]];
      E.cap-=d;
      e[u][E.rev].cap+=d;
    }
  }
  return res;
}

int main()
{
  int n;
  vector<Segment> vs,vt;
  Point st;
  double ans=0.0;

  cin>>n;
  cin>>st.x>>st.y;
  for(int i=0;i<n;i++){
    Point a,b;
    cin>>a.x>>a.y>>b.x>>b.y;
    Segment s(a,b);
     vt.push_back(Segment(a,b));
    ans+=abs(b-a);
  }

  int s=vt.size()*2;
  int t=s+1;
  v=t+1;
  for(int i=0;i<vt.size();i++){
    for(int j=0;j<vt.size();j++){ 
      add_edge(i,j+vt.size(),1,abs(vt[i].p2-vt[j].p1));
    }
  }
  for(int i=0;i<vt.size();i++){
    add_edge(s,i,1,0);
    add_edge(i+vt.size(),t,1,0);
  }
  printf("%.10f\n",ans+min_cost_flow(s,t,vt.size()));
  return 0;
}