WA #13 求调

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <queue>
#include <cmath>
#define double long double

using namespace std;

constexpr int N = 8e4 + 5, M = 2e6 + 5, inf = 2e9;
int n, s, t;

int head[N], nxt[M], ver[M], cap[M], tot = 1;
double cost[M];
inline void add (int a, int b, int f, double w) {
    ver[++ tot] = b, cap[tot] = f, cost[tot] = w;
    nxt[tot] = head[a], head[a] = tot;
}

struct Node {
    int x, y;
} node[N];
inline int asson (int id) {
    return id;
}
inline int asfath (int id) {
    return id + n;
}
inline double count (int x, int y) {
    return sqrtl(1.0 * (node[x].x - node[y].x) * (node[x].x - node[y].x) + \
                1.0 * (node[x].y - node[y].y) * (node[x].y - node[y].y));
}

bool inque[N];
int flow[N];
double dis[N];
int pre[N], com[N];
inline bool SPFA () {
    queue <int> q;
    for (int i = 0; i <= t; ++ i) inque[i] = false, dis[i] = inf, flow[i] = inf;
    inque[s] = true;
    dis[s] = 0;
    q.push(s);
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int i = head[x]; i; i = nxt[i]) {
            int y = ver[i];
            if (cap[i] and dis[y] > dis[x] + cost[i]) {
                dis[y] = dis[x] + cost[i];
                pre[y] = x;
                com[y] = i;
                flow[y] = min(flow[x], cap[i]);
                if (!inque[y]) {
                    inque[y] = true;
                    q.push(y);
                }
            }
        }
    }
    return dis[t] < inf;
}
inline double MCF () {
    double res = 0;
    int sum = 0;
    while (SPFA()) {
        res += dis[t] * flow[t], sum += flow[t];
        for (int i = t; i != s; i = pre[i]) {
            cap[com[i]] -= flow[t];
            cap[com[i] ^ 1] += flow[t];
        }
    }
    if (sum != n - 1) return -1;
    return res;
}

int main () {
    cin >> n;
    for (int i = 1; i <= n; ++ i) {
        cin >> node[i].x >> node[i].y;
    }
    sort(node + 1, node + n + 1, [](Node A, Node B) {
        return A.y < B.y;
    });
    s = 0, t = n * 2 + 1;
    for (int i = 1; i <= n; ++ i) {
        add(s, asfath(i), 2, 0);
        add(asfath(i), s, 0, 0);
        add(asson(i), t, 1, 0);
        add(t, asson(i), 0, 0);
    }
    for (int i = 1; i <= n; ++ i) {
        for (int j = n; node[j].y > node[i].y; -- j) {
            add(asfath(j), asson(i), 1, count(i, j));
            add(asson(i), asfath(j), 0, -count(i, j));
        }
    }
    double gt = MCF();
    if (gt == -1) cout << "-1";
    else cout << fixed << setprecision(15) << gt;
    return 0;
}