Codeforces Round #170 (Div. 1) E. Binary Tree on Plane

http://codeforces.com/contest/277/problem/E

2 <= N <= 400

2차원 좌표 평면상에 N개의 점이 주어진다. 

점 i와 점 j가 있을 때 yi < yj 일 때만 점 i 에서 점 j 로 간선을 이을 수가 있다.

만약 점 i 에서 점 j 로 간선을 잇게 되면 점 i는 점 j의 부모노드가 되며 이 때 드는 비용은

점 i와 점 j의 거리만큼이다. 이런식으로 N개의 점을 노드로하는 이진트리를 만들 때의 최소 비용을

구하는 문제이다. 물론 이진트리는 각각의 노드들의 자식의 수가 2개 이하인 트리이다.

N의 제한에서도 플로우의 냄새가 강하다. 뿐만 아니라 주어진 제한이 있으며

그 제한 내에서의 비용을 최소화 하는 문제, 플로우 중에서도 MCMF 라는 느낌을 받을 수가 있다.

그렇다면 주어진 제한이란 무엇일까? 

1. 모든 점은 부모가 최대 하나만 있어야 한다.

2. 모든 점의 자식은 최대 두개만 있어야 한다.

그리고 두 노드가 연결될 때에는 거리만큼의 비용이 든다. 그렇다면 이런 그래프를 만들어 볼 수 있다.

각각의 노드를 두 부분으로 나누어 생각해보자.

하나는 부모와 연결되는 IN 부분, 나머지 하나는 자식들과 연결되는 OUT 부분.

소스에서 부모 역할 노드로 가는 용량은 2(자식을 최대 두개까지 가질 수 있음) 비용은 0을 주고

자식 역할 노드에서 싱크로 가는 용량은 1(부모를 최대 한개까지 가질 수 있음) 비용은 0을 준다.

그리고 부모 역할 노드에서 자식 역할 노드로 가는 용량은 1(트리의 두 노드 사이의 간선은 최대 한개)

비용은 거리로 준다. 물론 간선은 y좌표를 비교하여 이어준다.

이렇게 MCMF 를 돌리면 최대 유량이 N - 1 이 나와야 한다. 왜냐 하면 트리에서 부모를 갖는 노드의 수는

N - 1개 이기 때문이다. N - 1 보다 작으면 트리를 만드는 것이 불가능한 것이고 만약 N - 1 이라면

그때의 최소 비용이 답이 된다.

#include <bits/stdc++.h>
#define pb push_back
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define fastio() ios_base::sync_with_stdio(0),cin.tie(0)
using namespace std;
typedef long long ll;
const int MOD = 1e9+7;
const int INF = 0x3c3c3c3c;
const long long INFL = 0x3c3c3c3c3c3c3c3c;
 
struct MCMF{
    struct edge{
        int to, cap;
        double cost;
        int rev;
    };
    int size, src, sink;
    vector<vector<edge> > G;
    vector<double> dist;
    vector<int> par, edgeIdx;
    MCMF(int size, int src, int sink){
        G = vector<vector<edge> >(size);
        par = vector<int>(size);
        edgeIdx = vector<int>(size);
        this->size = size;
        this->src = src;
        this->sink = sink;
    }
    bool spfa(){
        vector<bool> inQ = vector<bool>(size, false);
        queue<int> q;
        q.push(src);
        inQ[src] = true;
        dist[src] = 0;
        while(!q.empty()){
            int here = q.front();
            q.pop();
            inQ[here] = false;
            for(int i = 0 ; i < (int)G[here].size(); i++){
                auto e = G[here][i];
                if(e.cap > 0 && dist[here] + e.cost < dist[e.to]) {
                    dist[e.to] = dist[here] + e.cost;
                    par[e.to] = here;
                    edgeIdx[e.to] = i;
                    if(!inQ[e.to]) q.push(e.to), inQ[e.to] = true;
                }
            }
        }
        return dist[sink] != INF;
    }
    pair<int,double> getMCMF(){
        int maxFlow = 0;
        double minCost = 0;
        while(1){
            dist = vector<double>(size, INF);
            if(!spfa()) break;
            int minFlow = INF;
            double costSum = 0;
            for(int p = sink; p != src; p = par[p]){
                auto& e = G[par[p]][edgeIdx[p]];
                minFlow = min(minFlow, e.cap);
                costSum += e.cost;
            }
            for(int p = sink; p != src; p = par[p]){
                auto& e = G[par[p]][edgeIdx[p]];
                e.cap -= minFlow;
                G[e.to][e.rev].cap += minFlow;
            }
            maxFlow += minFlow;
            minCost += costSum * minFlow;
        }
        return {maxFlow, minCost};
    }
    void addEdge(int from, int to, int cap, double cost){
        G[from].push_back({to, cap, cost, (int)G[to].size()});
        G[to].push_back({from, 0, -cost, (int)G[from].size()-1});
    }
};
 
struct point{int x, y;};
bool cmp(point& a, point& b) {
    return a.y > b.y;
}
vector<point> points;
int N;
int NODE(int x){return 2 + x;}
int IN(int x){return 2 * x;}
int OUT(int x){return 2 * x + 1;}
double dist(point& a, point& b){
    return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
int main() {
    int src = 0, sink = 1;
    fastio();
    cin >> N;
    MCMF mcmf(2 * (N + 2), src, sink);
    for(int i = 0 ; i < N; i++){
        int x, y;
        cin >> x >> y;
        points.push_back(point{x, y});
    }
    sort(all(points), cmp);
    for(int i = 0 ; i < N; i++){
        for(int j = i + 1; j < N; j++){
            if(points[i].y == points[j].y) continue;
            mcmf.addEdge(OUT(NODE(i)), IN(NODE(j)), 1, dist(points[i], points[j]));
        }
        mcmf.addEdge(src, OUT(NODE(i)), 2, 0);
        mcmf.addEdge(IN(NODE(i)), sink, 1, 0);
    }
    auto ret = mcmf.getMCMF();
    if(ret.first != N - 1) return !printf("-1");
 
    cout.precision(17);
    cout << fixed << ret.second;
    
 
    return 0;
}