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>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 2005
#define ADD 1000


//辺を表す構造体{行先、容量、コスト、逆辺のインデックス}
struct Edge{
	Edge(int arg_to,int arg_capacity,double arg_cost,int arg_rev_index){
		to = arg_to;
		capacity = arg_capacity;
		cost = arg_cost;
		rev_index = arg_rev_index;
	}

	int to,capacity,rev_index;
	double cost;
};

struct Point{
	void set(int arg_x,int arg_y){
		x = arg_x;
		y = arg_y;
	}
	int x,y;
};

struct Info{
	Info(int arg_x,int arg_y,int arg_diff){
		x = arg_x;
		y = arg_y;
		diff = arg_diff;
	}
	int x,y,diff;
};

int V; //頂点数
vector<Edge> G[NUM]; //グラフの隣接リスト表現
double dist[NUM]; //最短距離
int pre_node[NUM],pre_edge[NUM]; //直前の頂点と辺

int num_line;
int in_num[NUM][NUM],out_num[NUM][NUM];
int point_index;
int index_FROM[NUM],index_TO[NUM];
Point start;
Point point[NUM];
vector<Info> FROM,TO;

//fromからtoへ向かう容量capacity,コストcostの辺をグラフに追加する
void add_edge(int from,int to,int capacity,double cost){
	G[from].push_back(Edge(to,capacity,cost,G[to].size()));
	G[to].push_back(Edge(from,0,-cost,G[from].size()-1));
}

//sourceからsinkへの、流量flowの最小費用流を求める
//流せない場合は-1を返す
double min_cost_flow(int source,int sink,int flow){

	double ret = 0;
	while(flow > 0){
		//ベルマンフォード方により、source-sink間最短経路を求める
		for(int i = 0; i < V; i++)dist[i] = BIG_NUM;
		dist[source] = 0;
		bool update = true;

		int dog = 0;

		while(update){

			update = false;
			for(int node_id = 0; node_id < V; node_id++){
				if(fabs(dist[node_id]-BIG_NUM) < EPS)continue;
				for(int i = 0; i < G[node_id].size(); i++){
					Edge &e = G[node_id][i];
					if(e.capacity > 0 && dist[e.to] > dist[node_id]+e.cost+EPS){
						dist[e.to] = dist[node_id]+e.cost; //node_idを経由した方が早い場合
						pre_node[e.to] = node_id;
						pre_edge[e.to] = i;
						update = true;
					}
				}
			}
		}

		if(fabs(dist[sink]-BIG_NUM) < EPS){
			//これ以上流せない
			return -1;
		}

		//source-sink間最短路に沿って目いっぱい流す
		int tmp_flow = flow;

		int dk = 0;

		for(int node_id = sink; node_id != source; node_id = pre_node[node_id]){

			tmp_flow = min(tmp_flow,G[pre_node[node_id]][pre_edge[node_id]].capacity);
		}
		flow -= tmp_flow;

		ret += tmp_flow*dist[sink];
		for(int node_id = sink; node_id != source; node_id = pre_node[node_id]){
			Edge &e = G[pre_node[node_id]][pre_edge[node_id]];
			e.capacity -= tmp_flow;
			G[node_id][e.rev_index].capacity += tmp_flow;
		}
	}
	return ret;
}


void add(Point& tmp){

	tmp.x += ADD;
	tmp.y += ADD;
}

double calc_dist(Point a,Point b){

	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

double calc_dist(Info a,Info b){

	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

int main(){

	for(int x = 0; x < NUM; x++){
		for(int y = 0; y < NUM; y++){
			in_num[x][y] = 0;
			out_num[x][y] = 0;
		}
	}

	scanf("%d",&num_line);
	scanf("%d %d",&start.x,&start.y);

	add(start);

	point_index = 0;
	double ans = 0;

	for(int loop = 0; loop < num_line; loop++){

		//from
		scanf("%d %d",&point[point_index].x,&point[point_index].y);
		add(point[point_index]);
		out_num[point[point_index].x][point[point_index].y] += 1;

		point_index++;

		//to
		scanf("%d %d",&point[point_index].x,&point[point_index].y);
		add(point[point_index]);
		in_num[point[point_index].x][point[point_index].y] += 1;

		ans += calc_dist(point[point_index-1],point[point_index]);

		point_index++;
	}

	for(int x = 0; x < NUM; x++){
		for(int y = 0; y < NUM; y++){
			if(in_num[x][y] == out_num[x][y])continue;

			if(in_num[x][y] > out_num[x][y]){

				FROM.push_back(Info(x,y,in_num[x][y]-out_num[x][y]));

			}else{

				TO.push_back(Info(x,y,out_num[x][y]-in_num[x][y]));
			}
		}
	}

	int FLOW = 0;
	int source = 0,sink = 1;
	int index = 2;

	for(int i = 0; i < FROM.size(); i++){

		index_FROM[i] = index++;
		FLOW += FROM[i].diff;
		add_edge(source,index_FROM[i],FROM[i].diff,0);
	}

	int to_sum = 0;

	for(int i = 0; i < TO.size(); i++){

		index_TO[i] = index++;
		add_edge(index_TO[i],sink,TO[i].diff,0);
		to_sum += TO[i].diff;
	}

	for(int i = 0; i < FROM.size(); i++){
		for(int k = 0; k < TO.size(); k++){
			add_edge(index_FROM[i],index_TO[k],1,calc_dist(FROM[i],TO[k]));
		}
	}

	V = index;

	ans += min_cost_flow(source,sink,FLOW);

	printf("%.10lf\n",ans);

	return 0;
}