Submission #84065

---

Source Code Expand

#include <iostream>
#include <iomanip>
#include <vector>
#include <map>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstring>

#define rep(i,n) for(int i=0;i<(n);i++)
using namespace std;

typedef pair<double, double> P;

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

const double eps = 1e-8;
const double INF = 1e100;
const int maxV = 102;

int V;
vector<edge> G[maxV];
bool used[maxV];
double dist[maxV];
int prevv[maxV], preve[maxV];

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

double min_cost_flow(int s, int t, 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] > 1e10) 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 > eps) {
                        dist[e.to] = dist[v] + e.cost;
                        prevv[e.to] = v;
                        preve[e.to] = i;
                        update = true;
                    }
                }
            }
        }

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

double dis(P a, P b) {
    return sqrt((a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second));
}

int main() {
    int n;
    double ans = 0;
    cin >> n;
    V = 102;
    vector<P> l,r;
    rep(i, n) {
        int x,y;
        cin >> x >> y;
        if (x == 0)continue;
        if (x < 0) l.push_back(make_pair(-x,y));
        else r.push_back(make_pair(x,y));
        ans += abs(x);
    }

    double fmax = 0;
    rep(f,51) {
        rep(i,102)G[i].clear();
        rep(i, l.size()) {
            add_edge(100, i, 1, 0);
        }
        rep(i, r.size()) {
            add_edge(l.size() + i, 101, 1, 0);
        }
        rep(i, l.size()) {
            rep(j, r.size()) {
                if ((l[i].first + r[j].first - dis(l[i], r[j])) > 0)
                    add_edge(i, l.size() + j, 1, -(l[i].first + r[j].first - dis(l[i], r[j])));
            }
        }

        fmax = max(fmax, -min_cost_flow(100, 101, f + 1));
    }
    
    cout << setprecision(10);
    cout << ans - fmax << endl;
    return 0;
}

Submission Info

Judge Result