Submission #83775

---

Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include<cassert>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include<bitset>

#define REP(i,b,n) for(int i=b;i<(int)n;i++)
#define rep(i,n)   REP(i,0,n)
#define ALL(C)     (C).begin(),(C).end()
#define FOR(it,o)  for(__typeof((o).begin()) it=(o).begin(); it!=(o).end(); ++it)
#define dbg(x) cout << __LINE__ << ' ' << #x << " = " << (x) << endl


typedef long long ll;

using namespace std;

const int MAX_V = 1000;
const double INF = 1e9;
 
class State{
public:
  double cost;
  int pos;
  bool operator<(const State &s)const{
    return cost > s.cost;
  }
};
 
class Edge{
public:
  int to, cap;
  double cost;
  int rev;
};
 
int V;
double dist[MAX_V];
int prevv[MAX_V], preve[MAX_V];//頂点数、ポテンシャル、距離、前の頂点、前のエッジ
vector<Edge> G[MAX_V];
 
void addEdge(int from, int to, int cap, double cost){
  G[from].push_back((Edge){to, cap, cost, G[to].size()});
  G[to].push_back((Edge){from, 0, -cost, G[from].size()-1});
}
 
double min_cost_flow(int s, int t, int f){
  double ret = 0;
  while(f>0){
    rep(i, V)dist[i] = INF;
    dist[s] = 0;
    bool update = true;
    while(update){
      update =false;
      rep(v, V){
	if(dist[v] == INF)continue;
	rep(i, G[v].size()){
	  Edge &e = G[v][i];
	  if(e.cap >0 && dist[e.to] > dist[v] + e.cost){
	    dist[e.to] = dist[v] + e.cost;
	    prevv[e.to] = v;
	    preve[e.to] = i;
	    update = true;
	  }
	}
      }
    }
    if(dist[t] == INF)return 0;

    //増加路に流す
    int mini = f;
    for(int v = t;v != s; v = prevv[v]){
      mini = min(mini, G[prevv[v]][preve[v]].cap);
    }
    f -= mini;
    ret += mini * dist[t];
    for(int v = t; v != s; v= prevv[v]){
      Edge &e = G[prevv[v]][preve[v]];
      e.cap -= mini;
      G[v][e.rev].cap += mini;
    }
  }
  return ret;
}

class P{
public:
  int x, y;
};

const int N = 100;

P p[N];

double getDist(P p1, P p2){
  double x = abs(p1.x) - abs(p2.x);
  double y = p1.y - p2.y;
  return sqrt(x*x + y*y);
}

int main(){
  int n;
  while(cin >> n){
    rep(i, MAX_V)G[i].clear();
    rep(i, n){
      cin >> p[i].x >> p[i].y;
    }
    vector<P> left, right;
    double ans = 0;
    rep(i, n){
      ans += abs(p[i].x);
      if(p[i].x < 0)left.push_back(p[i]);
      else if(p[i].x >0)right.push_back(p[i]);
    }
    int L = left.size(), R = right.size();
    V = L + R + 2;
    rep(i, L){
      addEdge(L+R, i, 1, 0);
    }
    rep(i, R){
      addEdge(L+i, L+R+1, 1, 0);
    }
    rep(i, L){
      rep(j, R){
	addEdge(i, L+j, 1, min(getDist(left[i], right[j]) - (double)abs(left[i].x) - (double)abs(right[j].x), 0.));
      }
    }
    printf("%.9lf\n", ans + min_cost_flow(L+R, L+R+1, min(L, R)));
  }
  return 0;
}

Submission Info

Judge Result