网络流 TLE on #14

#include<bits/stdc++.h>
using namespace std;

const int N = 1e6 + 106;

int n, idx[N], nd_sz, S, T;
struct edge {
    int u, v, w, next;
    double c;
}e[N << 1]; int e_sz = 1, h[N];
struct coord {
    int x, y;
}cd[N];

double Dist(coord x, coord y) {
    return sqrt((double)((x.x - y.x) * (x.x - y.x) + (x.y - y.y) * (x.y - y.y)));
}

void cnt(int u, int v, int w, double c) {
    e[++e_sz].u = u, e[e_sz].v = v, e[e_sz].w = w, e[e_sz].c = c, e[e_sz].next = h[u], h[u] = e_sz;
    return;
}

void flow_cnt(int u, int v, int w, double c) {
    cnt(u, v, w, c), cnt(v, u, 0, -c);
    return;
}

int MF; double MC;
double dist[N]; int cur[N];
queue<int> q; bool vis[N];

bool SPFA() {
    for(int i = 1; i <= nd_sz; i++)
        cur[i] = h[i], dist[i] = 0x3f3f3f3f, vis[i] = 0;
    queue<int>().swap(q);
    dist[S] = 0;
    vis[S] = 1;
    q.push(S);
    while(!q.empty()) {
        int x = q.front(); q.pop();
        vis[x] = 0;
        for(int i = h[x]; i; i = e[i].next) {
            int v = e[i].v, w = e[i].w; double c = e[i].c;
            if(!w) continue;
            if(dist[v] > dist[x] + c) {
                dist[v] = dist[x] + c;
                if(!vis[v]) {
                    vis[v] = 1;
                    q.push(v);
                }
            }
        }
    }
    return dist[T] != 0x3f3f3f3f;
}

int dfs(int x, int input) {
    if(x == T) return input;
    vis[x] = 1;
    int left = input;
    for(int i = cur[x]; i && left; i = e[i].next) {
        cur[x] = i;
        int v = e[i].v, w = e[i].w; double c = e[i].c;
        if(!vis[v] && (abs(dist[v] - dist[x] - c) <= 1e-4)) {
            int cost = dfs(v, min(left, w));
            e[i].w -= cost;
            e[i ^ 1].w += cost;
            left -= cost;
        }
    }
    vis[x] = 0;
    return input - left;
}

void dinic() {
    while(SPFA()) {
        while(1) {
            int res = dfs(S, 0x3f3f3f3f);
            MF += res;
            MC += res * dist[T];
            if(res <= 1e-6) break;
        }
    }
    return;
}

int main() {
    // freopen("E.in", "r", stdin);
    // freopen("E.out", "w", stdout);
    // int u = clock();
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        scanf("%d%d", &cd[i].x, &cd[i].y),
        idx[i] = 3 * i - 2;
    nd_sz = 3 * n + 2;
    S = 3 * n + 1, T = 3 * n + 2;
    for(int i = 1; i <= n; i++) {
        flow_cnt(S, idx[i], 1, 0);
        flow_cnt(S, idx[i] + 1, 1, 0);
        flow_cnt(idx[i] + 2, T, 1, 0);
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            if(cd[i].y > cd[j].y) {
                flow_cnt(idx[i], idx[j] + 2, 1, Dist(cd[i], cd[j]));
                flow_cnt(idx[i] + 1, idx[j] + 2, 1, Dist(cd[i], cd[j]));
            }
        }
    }
    dinic();
    if(MF != n - 1) printf("-1\n");
    else printf("%.10lf\n", MC);
    // cerr << clock() - u << endl;
    return 0;
}