G - No Cross Matching Editorial by en_translator
For points \(A\) and \(B\), let \(|AB|\) denote the length of the segment \(AB\).
In fact, the permutation \(R\) with the minimum \(\displaystyle \sum_{i=0}^{N}|P_i Q_{R_i}|\) is a solution to this problem.
証明
We will first show the following proposition:
If \(R\) does not satisfy the condition in the problem statement, there is \(R'\) such that \(\displaystyle \sum_{i=0}^{N}|P_i Q_{R'_i}| < \displaystyle \sum_{i=0}^{N}|P_i Q_{R_i}|\).
For \(R\) which does not satisfy the condition, suppose that segments \(P_a Q_{R_a}\) and \(P_b Q_{R_b}\) \((1 \leq a < b \leq N)\) intersect. Then, the permutation \(R'\) defined by \(R'_k= \left \{ \begin{array}{ll} R_k &(k \neq a \land k \neq b) \\ R_a &(k = b) \\ R_b &(k=a) \end{array} \right\} \) satisfies \(\displaystyle \sum_{i=0}^{N}|P_i Q_{R'_i}| < \displaystyle \sum_{i=0}^{N}|P_i Q_{R_i}|\). This is because, for the intersection \(X\) of the segments \(P_a Q_{R_a}\) and \(P_b Q_{R_b}\), the triangle inequality suggests that \(|P_aX|+|Q_{R_b}X|>|P_aQ_{R_b}|\) and \(|P_bX|+|Q_{R_a}X|>|P_bQ_{R_a}|\), which in turn imply \(|P_aQ_{R_a}|+|P_bQ_{R_b}|>|P_aQ_{R_b}|+|P_bQ_{R_a}|\).
Also, \(\displaystyle \sum_{i=0}^{N}|P_i Q_{R_i}|\) is bounded, so the minimum value exists. Thus, by the proposition above, if a permutation \(R\) minimizes \(\displaystyle \sum_{i=0}^{N}|P_i Q_{R_i}|\), then it satisfies the condition in the problem statement. (End of proof)
In order to find \(R\) that satisfies the minimum value, one has to solve a minimum-weight perfect matching problem, which can be solved with Hungarian algorithm or minimum cost flow algorithms. If you are new to minimum cost flow problem, please refer to articles on line (such as an article by drken, in Japanese). This time, the same problem is also available in Library Checker (Problem).
AtCoder Library (ACL) has minimum cost flow library, which facilitates the implementation. But note that ACL only guarantees integer types, and strictly speaking the behavior against floating-point cost type is not guaranteed. Thus, the cost of an edge should be defined as the actual cost multiplied by a common constant \(C\), rounded off. In our case, we need to set \(C\) to at least \(1.413 \times 10^{12}\) to prove the validity. For the maximum coordinate \(M\), the constant \(C\) must be in the order of at least \(O(M^3)\).
Nevertheless, in this problem you can get AC (accepted) verdict even if you use double
or long double
type for the cost to use in ACL.
#include "atcoder/mincostflow"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
static constexpr long double C = 1.5e12; //4/(sqrt(4999^2+5000^2)+sqrt(4997^2+4998^2)-2*sqrt(4998^2+4999^2))=1.413*10^12
int main() {
int n;
cin >> n;
vector<ll> xb(n), yb(n), xw(n), yw(n);
for (int i = 0; i < n; ++i) {
cin >> xb[i] >> yb[i];
}
for (int i = 0; i < n; ++i) {
cin >> xw[i] >> yw[i];
}
auto dist = [&](int i, int j) -> long double {
return sqrtl((xb[i] - xw[j]) * (xb[i] - xw[j]) + (yb[i] - yw[j]) * (yb[i] - yw[j]));
};
atcoder::mcf_graph<ll, ll> g(2 * n + 2);
int s = 2 * n, t = 2 * n + 1;
for (int i = 0; i < n; ++i) {
g.add_edge(s, i, 1, 0);
g.add_edge(i + n, t, 1, 0);
for (int j = 0; j < n; ++j) {
g.add_edge(i, j + n, 1, (ll)(dist(i, j) * C + 0.5));
}
}
auto [flow, cost] = g.flow(s, t);
assert(flow == n);
int edge_id = 0;
vector<int> ans(n);
for (int i = 0; i < n; ++i) {
edge_id += 2;
for (int j = 0; j < n; ++j) {
auto e = g.get_edge(edge_id);
if (e.flow == 1)
ans[i] = j + 1;
edge_id++;
}
}
for (int i = 0; i < n; ++i) {
cout << ans[i] << " \n"[i == n - 1];
}
}
posted:
last update: