\(\mathtt{UVA 1411}\) \(\mathtt{Ants}\)
\(\mathcal{Description}\)
给定一些黑点白点，要求一个黑点连接一个白点，并且所有线段都不相交。
\(\mathcal{Solution}\)
首先通过画图可以发现，要使所有线段都不相交可以使距离总和最小。所以题意就转化成为使距离总和最小的连接方式，自然联想到\(KM\)。我们可以先预处理出每一对白点和黑点之间的距离，因为要求的是最小连接方式，所以可以把距离取反来求最大值，限制条件为\(g[i] + b[i] = a[i][j]\)，\(a[i][j]\)是取反后的距离，\(g[i]\)是黑点的期望值，\(b[i]\)是白点的期望值，复杂度为\(O(n^3)\)。
\(\mathcal{Code}\)
#include<bits/stdc++.h>
using namespace std;
const int N = 110, INF = 1 << 30, Eps = 1e-9;
bool tfg[N], tfb[N];
int match[N], n,cnt ;
double a1[N], b1[N], a2[N], b2[N], a[N][N], b[N], g[N];
inline int read() {
int x = 0, k = 1; char c = getchar();
for (; c < 48 || c > 57; c = getchar()) k ^= (c == '-');
for (; c >= 48 && c <= 57; c = getchar()) x = x * 10 + (c ^ 48);
return k ? x : -x;
}
bool pd(int x) {
tfg[x] = true;
for (int i = 1; i <= n; i++)
if (fabs(g[x] + b[i] - a[x][i]) < Eps && !tfb[i]) {
tfb[i] = true;
if (match[i] == -1) {
match[i] = x;
return true;
}
if (pd(match[i])) {
match[i] = x;
return true;
}
}
return false;
}
inline void KM() {
memset(match, -1, sizeof(match));
memset(b, 0.0, sizeof(b));
for (int i = 1; i <= n; i++) {
g[i] = std::max(0.0, a[i][1]);
for (int j = 2; j <= n; j++)
g[i] = std::max(g[i], a[i][j]);
}
for (int i = 1; i <= n; i++) {
while (true) {
//printf("%d KM\n",i);
memset(tfb, false, sizeof(tfb));
memset(tfg, false, sizeof(tfg));
if (pd(i))
break;
double d = INF;
for (int j = 1; j <= n; j++)
if (tfg[j])
for (int k = 1; k <= n; k++)
if (!tfb[k])
d = std::min(d, g[j] + b[k] - a[j][k]);
// if (cnt<=5) printf("%d %.2lf YES\n",i,d);
for (int j = 1; j <= n; j++) {
if (tfg[j])
g[j] -= d;
if (tfb[j])
b[j] += d;
}
// if (i==1 && cnt<=5) for (int j=1; j<=n; j++) printf("%d %.2lf %.2lf\n",j,g[j],b[j]);
// cnt++;
}
}
}
inline double dist(double x, double y, double xx, double yy) {
return sqrt((x - xx) * (x - xx) + (y - yy) * (y - yy));
}
int main() {
while (scanf("%d", &n) != EOF) {
for (int i = 1; i <= n; i++)
scanf("%lf%lf", &a1[i], &b1[i]);
for (int i = 1; i <= n; i++)
scanf("%lf%lf", &a2[i], &b2[i]);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
a[j][i] = -dist(a1[i], b1[i], a2[j], b2[j]);
KM();
for (int i = 1; i <= n; i++)
printf("%d\n", match[i]);
}
return 0;
}