Codeforces277 E. Binary Tree on Plane 최소 비용 최대 흐름

Codeforces277 E. Binary Tree on Plane 최소 비용 최대 흐름

제목

사고방식

Code(467MS)

전송문:https://codeforces.com/contest/277/problem/E

제목

평면에 n개의 점(2≤n≤400)을 주고 이 점들로 두 갈래 나무를 만들어야 합니다.평면에 n개의 점(2≤n≤400)을 주고 이 점들로 두 갈래 나무를 만들어야 합니다.평면에 n개의 점(2≤n≤400)을 주고 이 점들로 두 갈래 나무를 만들어야 합니다.각 모서리의 값을 두 점 사이의 유클리드 거리로 정의합니다.권한과 가장 작은 두 갈래 나무를 구하고 출력합니다.각 모서리의 값을 두 점 사이의 유클리드 거리로 정의합니다.권한과 가장 작은 두 갈래 나무를 구하고 출력합니다.각 모서리의 값을 두 점 사이의 유클리드 거리로 정의합니다.권한과 가장 작은 두 갈래 나무를 구하고 출력합니다.점 i의 y 좌표가 j의 y 좌표보다 크면 점 i는 점 j의 아버지가 될 수 있다.점 i의 y 좌표가 j의 y 좌표보다 크면 점 i는 점 j의 아버지가 될 수 있다.점 i의 y 좌표가 j의 y 좌표보다 크면 점 i는 점 j의 아버지가 될 수 있다.조건을 충족시키는 두 갈래 나무가 없으면 출력−1입니다.조건을 충족시키는 두 갈래 나무가 없으면 출력−1입니다.조건을 충족시키는 두 갈래 나무가 없으면 출력−1입니다.

생각

두 갈래 나무의 제한이 없다면 가장 작은 나무가 생기는 것이다.네트워크 흐름 모델을 고려할 수 있다.두 갈래 나무의 제한이 없다면 가장 작은 나무가 생기는 것이다.네트워크 흐름 모델을 고려할 수 있다.두 갈래 나무의 제한이 없다면 가장 작은 나무가 생기는 것이다.네트워크 흐름 모델을 고려할 수 있다.
두 갈래 나무에 대해 하나의 뿌리 노드는 최대 두 개의 하위 노드를 연결할 수 있다.두 갈래 나무에 대해 하나의 뿌리 노드는 최대 두 개의 하위 노드를 연결할 수 있다.두 갈래 나무에 대해 하나의 뿌리 노드는 최대 두 개의 하위 노드를 연결할 수 있다.
그래서 우리는 하나의 점 i에 대해 분해를 하고 뿌리 노드 i와 하위 노드 n+i로 분해한다.그래서 우리는 하나의 점 i에 대해 분해를 하고 뿌리 노드 i와 하위 노드 n+i로 분해한다.그래서 우리는 하나의 점 i에 대해 분해를 하고 뿌리 노드 i와 하위 노드 n+i로 분해한다.
두 갈래 나무의 가장자리는 반드시 뿌리 결점 연결자 노드이고 권치는 두 점의 유럽식 거리이다.두 갈래 나무의 가장자리는 반드시 뿌리 결점 연결자 노드이고 권치는 두 점의 유럽식 거리이다.두 갈래 나무의 가장자리는 반드시 뿌리 결점 연결자 노드이고 권치는 두 점의 유럽식 거리이다.
루트 노드는 최대 1개, 하위 노드는 최대 2개이기 때문에 우리는 위에서 말한 바와 같이 루트 노드는 최대 1개, 하위 노드는 최대 2개이다. 그래서 우리는 위에서 말한 바와 같이 루트 노드는 최대 1개, 하위 노드는 최대 2개이다. 그래서 우리는 위에서 말한 바와 같이 ad(점 i, 점 j, 흐름, 비용)add(점 i, 점 j, 흐름, 비용)add(점 i, 점 j, 흐름, 비용)add(점 j, 비용)add(점 i, 점 j, 흐름, 비용)

원점 연결 서브노드−ad(s, n+i, 2, 0)는 각 노드가 최대 두 개의 서브노드를 나타낸다.원점 연결 서브노드-add(s, n+i, 2, 0)는 각 노드마다 최대 두 개의 서브노드를 나타낸다.원점 연결 서브노드 −add(s, n+i, 2,0)는 각 노드가 최대 두 개의 서브노드를 나타낸다.

근결점 연결환점−ad(i,t,1,0)은 각 노드가 가장 많은 근노드를 나타낸다.루트 결점 연결 외환점-add(i,t,1,0)는 각 노드가 가장 많은 루트 노드를 나타낸다.루트 결점 연결 외환점−add(i,t,1,0)는 각 노드가 가장 많은 루트 노드를 나타낸다.

루트 노드 연결 서브노드−a d(n+i, j, 1, D i(i, j), i가 j의 루트 노드가 될 수 있음을 나타낸다.루트 노드는 하위 노드-add(n+i, j, 1, Dis(i, j)를 연결하여 i가 j의 루트가 될 수 있음을 나타낸다.루트 노드 연결 서브노드 −add(n+i, j, 1, Dis(i, j), i가 j의 루트가 될 수 있음을 나타낸다.

C M F를 한 번 뛰고 만류하면 m a x f l o w = n−1이면 이 두 갈래 나무가 존재하고 그렇지 않으면 출력−1이 됩니다.MCMF를 한 번 뛰고 만류가 maxflow=n-1이면 이 두 갈래 나무가 존재하고 그렇지 않으면 출력-1이 됩니다.MCMF를 한 번 뛰고 만류가 maxflow=n−1이면 이 두 갈래 나무가 존재하고 그렇지 않으면 출력−1입니다.

Code（467MS）

#include "bits/stdc++.h"

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

#define endl "
"
#define pb push_back
#define mem(a, b) memset(a , b , sizeof(a))
#define FOR(i, x, n) for(int i = x;i <= n; i++)

const int INF = 0x3f3f3f3f;
// const ll mod = 998244353;
// const ll mod = 1e9 + 7;
const double eps = 1e-6;
const double PI = acos(-1);
const double R = 0.57721566490153286060651209;

const int maxn = 1005;      // 

struct Edge {
     
    int from, to, cap, flow;
    double cost;

    Edge(int u, int v, int c, int f, double cc)
            : from(u), to(v), cap(c), flow(f), cost(cc) {
     }
};

struct MCMF {
     
    int n, m;
    vector<Edge> edges;
    vector<int> G[maxn];
    int inq[maxn];  // 
    double d[maxn];    //bellmanford
    int p[maxn];    // 
    int a[maxn];    // 
    void init(int n) {
     
        this->n = n;
        for (int i = 0; i <= n; ++i) G[i].clear();
        edges.clear();
    }

    void addEdge(int from, int to, int cap, double cost) {
     
        edges.emplace_back(Edge(from, to, cap, 0, cost));
        edges.emplace_back(Edge(to, from, 0, 0, -cost));
        m = int(edges.size());
        G[from].emplace_back(m - 2);
        G[to].emplace_back(m - 1);
    }

    bool spfa(int s, int t, int &flow, double &cost) {
     
        for (int i = 1; i <= n; ++i) d[i] = INF;
        memset(inq, 0, sizeof(inq));
        d[s] = 0;
        inq[s] = 1;
        p[s] = 0;
        queue<int> q;
        a[s] = INF;
        q.push(s);
        while (!q.empty()) {
     
            int u = q.front();
            q.pop();
            inq[u] = 0;
            for (int i = 0; i < int(G[u].size()); ++i) {
     
                Edge &e = edges[G[u][i]];
                if (e.cap > e.flow && d[e.to] > d[u] + e.cost) {
     
                    d[e.to] = d[u] + e.cost;
                    p[e.to] = G[u][i];
                    a[e.to] = min(a[u], e.cap - e.flow);
                    if (!inq[e.to]) {
     
                        q.push(e.to);
                        inq[e.to] = 1;
                    }
                }
            }
        }
        if (d[t] == INF) return false;
        flow += a[t];
        cost += d[t] * a[t];
        for (int u = t; u != s; u = edges[p[u]].from) {
     
            edges[p[u]].flow += a[t];
            edges[p[u] ^ 1].flow -= a[t];
        }
        return true;
    }

    int MincostMaxflow(int s, int t, double &cost) {
     
        int flow = 0;
        cost = 0;
        while (spfa(s, t, flow, cost));
        return flow;
    }
} mcmf;

double Dis(pair<double, double> a, pair<double, double> b) {
     
    return sqrt(((a.first - b.first) * (a.first - b.first)) + (a.second - b.second) * (a.second - b.second));
}

bool cmp(pair<double, double> a, pair<double, double> b) {
     
    return a.second == b.second ? a.first < b.first : a.second > b.second;
}

void solve() {
     
    int n;
    scanf("%d",&n);
    mcmf.init(2 * n + 1);
    int s = 0, t = 2 * n + 1;
    pair<double, double> p[maxn];
    for(int i = 1;i <= n; i++) {
     
        scanf("%lf%lf",&p[i].first, &p[i].second);
        mcmf.addEdge(s, n + i, 2, 0); //  
        mcmf.addEdge(i, t, 1, 0); //  
    }
    sort(p + 1, p + n + 1, cmp);
    if(p[1].second == p[2].second) {
      //  ？ 
        printf("-1
");
        return ;
    }
    for(int i = 1;i <= n; i++) {
     
        for(int j = i + 1;j <= n; j++) {
     
            if(p[i].second == p[j].second) continue;
            mcmf.addEdge(n + i, j, 1, Dis(p[i], p[j]));
        }
    }
    double mincost;
    auto ans = mcmf.MincostMaxflow(s, t, mincost);
    if(ans == n - 1) printf("%.8lf
",mincost);
    else printf("-1
");
}

signed main() {
     
    solve();
}