蚂蚁
C++ 代码
/*
题目要求最后所有线段都不相交。
那么试想,如果第 i1 个白点连第 j1 个黑点,第 i2 个白点连第 j2 个黑点,并且线段 (i1, j1) 和线段 (i2, j2) 相交,
那么如果交换一下,让 i1 连 j2,i2 连 j1,这样两条线段就不会相交,根据三角形的性质可知,两条交换后的线段的长度
之和一定变小。
所以求所有线段的长度之和最小的方案,所有线段一定互不相交。
如果将所有白点作为左部节点,所有黑点作为右部节点,可以发现这是一个二分图,因此求的就是二分图的带权最小匹配。
由于每个白点都一定能对应一个黑点,因此是一个二分图的完备匹配,所以可以用 KM 算法。
KM 算法求的是二分图的带权的最大完备匹配,这里可以将所有边的权值取反,那么就转化为最大匹配了。
*/
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
typedef pair<int, int> PII;
const int N = 110;
const double eps = 1e-10;
int n;
double w[N][N]; //记录所有左部节点和所有右部节点之间的距离的取反值
//la[i] 表示左部第i个节点的顶标
//lb[j] 表示右部第j个节点的顶标
//upd[j] 表示与右部节点 j 匹配的所有左部节点 i 中,la[i] + lb[j] - w[i][j] 的最小值
double la[N], lb[N], upd[N];
bool ast[N], bst[N]; //记录左、右部节点是否在交错树中
int match[N]; //记录每个右部节点匹配了哪一个左部节点
int last[N]; //记录每个右部节点的最小upd值对应的左部节点
PII a[N], b[N]; //记录所有左、右部节点的坐标
double get_dist(int i, int j) //计算左部第i个节点和右部第j个节点之间的距离
{
double x = a[i].first - b[j].first, y = a[i].second - b[j].second;
return sqrt(x * x + y * y);
}
bool find(int u, int fa) //为左部节点u进行匹配,fa表示和左部节点u匹配的右部节点
{
ast[u] = true; //将当前点加入交错树
for(int i = 1; i <= n; i++)
if(!bst[i]) //枚举不在交错树中的右部节点
if(fabs(la[u] + lb[i] - w[u][i]) < eps) //la[u] + lb[i] = w[u][i] -> 相等子图
{
bst[i] = true;
last[i] = fa;
if(!match[i] || find(match[i], i))
{
match[i] = u;
return true; //匹配成功
}
}
else if(upd[i] > la[u] + lb[i] - w[u][i] + eps) //能更新upd值
{
upd[i] = la[u] + lb[i] - w[u][i];
last[i] = fa;
}
return false; //到这说明匹配失败
}
void km() //二分图的带权最大匹配
{
//初始化所有节点的顶标
for(int i = 1; i <= n; i++)
{
la[i] = -1e20; //左部节点的顶标设为负无穷
lb[i] = 0; //右部节点的顶标设为0
for(int j = 1; j <= n; j++)
la[i] = max(la[i], w[i][j]); //记录la[i]的最大值,保证 la[i] + lb[j] >= w[i][j]
}
for(int i = 1; i <= n; i++) //为所有左部节点进行匹配
{
//初始化
memset(ast, 0, sizeof ast);
memset(bst, 0, sizeof bst);
for(int j = 1; j <= n; j++) upd[j] = 1e20;
//从右部节点st匹配的左节点match[st]开始匹配,一开始假设有一条0-i的匹配
int st = 0;
match[0] = i;
while(match[st]) //当到达一个非匹配点st时停止
{
double delta = 1e20; //记录最小的upd值
if(find(match[st], st)) break; //如果匹配成功,直接跳出
//否则需要修改顶标,在这之前要找出最小的upd值
for(int j = 1; j <= n; j++)
if(!bst[j] && delta > upd[j]) //如果当前点不在交错树中,且upd值更小
{
delta = upd[j]; //更新
st = j; //下一次直接从最小边开始搜索
}
//修改顶标
for(int j = 1; j <= n; j++)
{
if(ast[j]) la[j] -= delta; //将交错树中的左部节点减去最小upd值
if(bst[j]) lb[j] += delta; //将交错树中的右部节点加上最小upd值
else upd[j] -= delta; //能匹配到的左部节点已经减去最小upd值,对应的upd值也需要减去最小upd值
}
bst[st] = true; //将当前右部节点加入交错树
}
while(st) //倒退更新增广路径
{
match[st] = match[last[st]];
st = last[st];
}
}
}
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d%d", &b[i].first, &b[i].second); //右部节点
for(int i = 1; i <= n; i++) scanf("%d%d", &a[i].first, &a[i].second); //左部节点
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
w[i][j] = -get_dist(i, j); //存储距离的取反值作为边的权值
km(); //二分图的带权最大匹配
for(int i = 1; i <= n; i++) printf("%d\n", match[i]);
return 0;
}