题意：
给出n个白点和n个黑点的坐标，要求用n条不相交的线段把它们连接起来，其中每条线段恰好连接一个白点和一个黑点，每个点恰好连接到一条线段
解析：
带入负的欧几里得距离求就好了
假设a1-b1 与 a2-b2相交 则dis(a1, b1) + dis(a2, b2) 一定大于 dis(a1, b2) + dis(a2, b1)
四边形的对角线一定大于两条对边。。。
所以。。边的权值取负的欧几里得距离。。来一次km就好了 km是求最大 而负的最大 对应整的最小 而整的最小 又能对应不相交
#include <iostream>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <cmath>
#include <algorithm>
#include <vector>
#define mem(a, b) memset(a, b, sizeof(a))
using namespace std;
const int maxn = , INF = 0x7fffffff;
const double eps = 1e-;
int usedx[maxn], usedy[maxn], cx[maxn], cy[maxn];
int nx, ny, n, max_value;
double minn;
double w[maxn][maxn], bx[maxn], by[maxn], slack[maxn];
struct node
{
double x, y;
}Node[maxn], Edge[maxn]; int dcmp(double x)
{
if(fabs(x) < eps) return ; else return x < ? - : ;
} bool dfs(int u)
{
usedx[u] = ;
for(int i=; i<=ny; i++)
{
if(usedy[i] == )
{
double t = bx[u] + by[i] - w[u][i];
if(dcmp(t) == )
{
usedy[i] = ;
if(cy[i] == - || dfs(cy[i]))
{
cy[i] = u;
cx[u] = i;
return true;
}
}
else
slack[i] = min(slack[i], t);
}
}
return false;
} void km()
{
mem(cx, -);
mem(cy, -);
mem(by, );
for(int i=; i<=n; i++)
{
bx[i] = -INF;
for(int j=; j<=n; j++)
bx[i] = max(bx[i], w[i][j]);
}
for(int i=; i<=n; i++)
{
for(int j=; j<=n; j++)
slack[j] = INF;
while()
{
mem(usedx, );
mem(usedy, );
if(dfs(i)) break;
double d = INF;
for(int j=; j<=n; j++)
if(!usedy[j])
d = min(d, slack[j]);
for(int j=; j<=n; j++)
if(usedx[j] != ) bx[j] -= d;
for(int j=; j<=n; j++)
if(usedy[j] != ) by[j] += d;
else slack[j] -= d;
}
}
} int main()
{
bool flag = true;
while(~scanf("%d",&n))
{
if(true) flag = false;
else printf("\n");
for(int i=; i<=n; i++)
{
scanf("%lf%lf", &Node[i].x, &Node[i].y);
}
for(int i=; i<=n; i++)
scanf("%lf%lf", &Edge[i].x, &Edge[i].y);
for(int i=; i<=n; i++)
for(int j=; j<=n; j++)
w[i][j] = -sqrt((Edge[i].x - Node[j].x)*(Edge[i].x - Node[j].x) + (Edge[i].y - Node[j].y)*(Edge[i].y - Node[j].y)); nx = ny = n;
km();
for(int i=; i<=n; i++)
printf("%d\n", cy[i]); }
return ;
}