题解：AT_abc373_g [ABC373G] No Cross Matching

RAYMOND_7 · 2024-10-01 10:05:18 · 题解

搬一下官方题解的证明

手画一下可以发现，交叉一定会导致总距离增大，这样可以转化为求匹配距离和最小，因为交点多距离小总可以调整为交点减少距离也变小。

结论是：距离最小的方案一定是要求的合法解之一。

直接跑最小费用流即可，或者偷懒写个调整法，n \le 300 所以能过。

调整法跑的非常快，最大点跑了 4 \text{ms}。

#include <bits/stdc++.h>

using namespace std;

#define For(i, l, r) for(int i = l; i <= r; i ++)

const int N = 310;

int n, m, a[N], b[N], c[N], d[N], p[N];

double PF(double x) {return x * x;}

double dis(int i, int j)
{
    return sqrt(PF(a[i] - c[j]) + PF(b[i] - d[j]));
}

int main()
{
    cin >> n;
    For(i, 1, n) cin >> a[i] >> b[i];
    For(i, 1, n) cin >> c[i] >> d[i];
    For(i, 1, n) p[i] = i;
    while(1)
    {
        int oper = 0;
        For(i, 1, n) For(j, 1, i - 1)
        {
            if(dis(i, p[j]) + dis(j, p[i]) < dis(i, p[i]) + dis(j, p[j]))
            {
                oper = 1;
                swap(p[i], p[j]);
            }
        }
        if(!oper) break;
    }
    For(i, 1, n) printf("%d ", p[i]);
    return 0;
}