Codeforces277 E. Binary Tree on Plane 最小费用最大流

传送门：https://codeforces.com/contest/277/problem/E

题意

给你平面上 n 个点 (2≤n≤400)，要求用这些点组成一个二叉树。 定义每条边的权值为两个点之间的欧几里得距离。求一个权值和最小的二叉树，并输出。 点 i 的 y 坐标比 j 的 y 坐标大，则点i可以成为点j的父亲。 如果不存在满足条件的二叉树，输出 −1 。

思路

如果没有二叉树的限制，那么就是最小生成树了。可以考虑网络流模型。

对于一个二叉树，一个根节点最多可以连接两个子节点。

所以我们对于一个点i，进行拆点，拆成根节点i和子节点n+i。

对于二叉树的边，一定是根结点连接子节点，权值为两点的欧式距离。

根节点最多1个，子节点最多两个，所以我们根据上面所述： add(点i，点j，流，费用)

  • 源点连接子节点-add(s, n + i, 2, 0)，表示每个节点最多两个子节点。
  • 根结点连接汇点-add(i, t, 1, 0)，表示每个节点最多一个根节点。
  • 根节点连接子节点-add(n+i,j,1,Dis(i,j))，表示i可以成为j的根节点。

跑一遍MCMF，如果满流即maxflow=n-1，则该二叉树存在，否则输出-1。

Code（467MS）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
##include "bits/stdc++.h"

using namespace std;

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

##define endl "\n"
##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\n");
        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\n",mincost);
    else printf("-1\n");
}

signed main() {
    solve();
}

本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2021/02/15/codeforces277-e/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！