Submission #495779

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <vector>
#include <numeric>
#include <iomanip>

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


using R = double;
constexpr R EPS = 1E-11;
R hungarian(const vector<vector<R>>& a){//{{{
    int n = a.size(), p, q;
    vector<R> fx(n, numeric_limits<R>::max()), fy(n, 0);
    vector<int> x(n, -1), y(n, -1);
    rep(i, n) rep(j, n) fx[i] = max(fx[i], a[i][j]);
    for(int i = 0; i < n; ){
        vector<int> t(n, -1), s(n+1, i);
        for(p=q=0; p <= q && x[i] < 0; ++p)
            for(int k = s[p], j=0; j < n && x[i] < 0; ++j)
                if(abs(fx[k] + fy[j] - a[k][j]) < EPS && t[j] < 0){
                    s[++q] = y[j], t[j] = k;
                    if(s[q] < 0) for(p = j; p >= 0; j = p)
                        y[j] = k = t[j], p = x[k], x[k] = j;
                }
        if(x[i] < 0){
            R d = numeric_limits<R>::max();
            rep(k, q+1) rep(j, n) if(t[j] < 0)
                d = min(d, fx[s[k]] + fy[j] - a[s[k]][j]);
            rep(j, n) fy[j] += (t[j] < 0 ? 0 : d);
            rep(k, q+1) fx[s[k]] -= d;
        }else ++i;
    }
    R res = 0;
    rep(i, n) res += a[i][x[i]];
    return res;
}//}}}

int main(){//{{{
    int n;
    cin >> n;
    int x, y; cin >> x >> y;
    vector<int> sx(n), sy(n), tx(n), ty(n);
    rep(i, n) cin >> sx[i] >> sy[i] >> tx[i] >> ty[i];
    vector<vector<R>> g(n, vector<R>(n));
    rep(i, n) rep(j, n) g[i][j] = -hypot(sx[i]-tx[j], sy[i]-ty[j]);
    R res = -hungarian(g);
    rep(i, n) res += hypot(sx[i] - tx[i], sy[i] - ty[i]);
    cout << fixed << setprecision(10) << res << endl;
    return 0;
}//}}}
// vim:set foldmethod=marker commentstring=//%s:

Submission Info

Judge Result