Submission #84904

---

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <cstdlib>
#include <cmath>
using namespace std;

#define MAX_V 500
#define INF 999999999

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

int V;
vector<edge> G[MAX_V];
double dist[MAX_V];
int prevv[MAX_V], preve[MAX_V];

void add_edge(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 g, int f){
  double res = 0;

  while(f > 0){
    fill(dist , dist + V , INF);
    dist[s] = 0;
    bool update = true;
    while(update){
      update = false;
      for(int v = 0; v < V; v++){
        if(dist[v] == INF) continue;
        for(int i = 0; i < G[v].size(); i++){
          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[g]== INF){
      return -1;
    }

    int d = f;
    for(int v = g; v != s; v = prevv[v]){
      d = min(d, G[prevv[v]][preve[v]].cap);
    }
    f -= d;
    res += d * dist[g];
    for(int v = g; v != s; v = prevv[v]){
      edge &e = G[prevv[v]][preve[v]];
      e.cap -= d;
      G[v][e.rev].cap += d;
    }
  }
  return res;
}

int main(){
  int n;

  while(cin >> n){
    double x[n], y[n];

    for(int i = 0; i < MAX_V; i++){
      G[i].clear();
    }

    for(int i = 0; i < n; i++){
      cin >> x[i] >> y[i];
    }

    //index
    //[0] : s
    //[1] : t
    //[2] ~ [2 + n - 1] : left
    //[2 + n] ~ [2 + n + n - 1] : right

    //s -> left
    for(int i = 2; i <= 2 + n - 1; i++){
      add_edge(0, i, 1, 0);
    }

    //right -> t
    for(int i = 2 + n; i <= 2 + n + n - 1; i++){
      add_edge(i, 1, 1, 0);
    }

    //left -> right
    for(int i = 0; i < n; i++){
      for(int j = 0; j < n; j++){
        if(i == j){
          add_edge(2 + i, 2 + n + j, 1, abs(x[i]));
          continue;
        }

        bool leftFlg = (x[i] < 0);
        bool rightFlg = (x[j] > 0);

        if(leftFlg && rightFlg){
          double dist = sqrt(pow(abs(y[i] - y[j]) / 2.0, 2) +
                             pow(abs(abs(x[i]) - abs(x[j])) / 2.0, 2));
          add_edge(2 + i, 2 + n + j, 1, 2 * dist);
        }
        else if(!leftFlg && !rightFlg){
          add_edge(2 + i, 2 + n + j, 1, 0);
        }
      }
    }

    V = n * 2 + 2;

    cout << fixed << setprecision(10) << min_cost_flow(0, 1, n) << endl;
  }
}

Submission Info

Judge Result