二分图带权匹配
权值即为两点之间的距离
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5,inf=1<<29;
const double eps=1e-6;
typedef long long ll;
typedef pair<int,int> pii;
#define mk(a,b) make_pair(a,b)
double edge[110][110], upd[110],la[110],lb[110];
struct Point{ double x,y;}a[maxn],b[maxn] ;
int n,match[110],vb[110],va[110];
double dis(Point a,Point b) { //距离
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
bool dfs(int x) { //匈牙利算法
va[x]=1; //左边
for(int y=1;y<=n;y++) {
if(!vb[y]) { //不在本交错树中
if(fabs(la[x]+lb[y]-edge[x][y]) < eps ){//满足相等子图条件
vb[y]=1;//右边加入交错树中(不管匹配边成功与否)
if(!match[y]||dfs(match[y]) ) { //进行匹配
match[y]=x; return true; //匹配成功
}
} else { //用于计算最小的delta
upd[y]=min(upd[y],la[x]+lb[y]-edge[x][y] ) ;
}
}
} return false ;
}
int KM() {
for(int i=1;i<=n;i++) { //顶标初始化
la[i]=-(1<<29);
lb[i]=0;
for(int j=1;j<=n;j++) //左边赋值为最大边权,右边为0
la[i]=max(la[i],edge[i][j]);
}
for(int i=1;i<=n;i++) { //对左边的各个点进行匹配
while(1) { //循环
memset(va,0,sizeof(va) ) ;
memset(vb,0,sizeof(vb) ) ;
fill(upd,upd+n+1,inf);//赋值
if(dfs(i)) break; //直到找到匹配边
double delta=inf;
for(int j=1;j<=n;j++) //找到最小的delta
if(!vb[j]) delta=min(delta,upd[j]) ;
for(int j=1;j<=n;j++) { //修改边权
if(va[j]) la[j]-=delta;
if(vb[j]) lb[j]+=delta;
}
}
}
}
int main(){
ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].y;
for(int j=1;j<=n;j++) cin>>b[j].x>>b[j].y;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
edge[i][j]=-dis(a[j],b[i]) ; //连边 白-->黑
KM();
//print
for(int i=1;i<=n;i++) cout<<match[i]<<'\n';
return 0;
}