易错点:
- 如果是double类型的数据,判断是否为零需要if(fabs(gap)<1e-10).
- 不直接使用delta的原因是会TLE,所以需要用if(va[i]&&!vb[j])剪枝
- 如果要开double类型的INF可以直接用1e12.
- 中间值转换成double类型可以使用value*1.0.
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
const int N=120;
const double INF=1e12;
double w[N][N],la[N],lb[N],delta;
int match[N],n;
bool va[N],vb[N];
bool dfs(int x){
va[x]=1;
for(int y=1;y<=n;y++){
if(vb[y])continue;
double gap=la[x]+lb[y]-w[x][y];
if(fabs(gap)<1e-10){
vb[y]=1;
if(!match[y]||dfs(match[y])){
match[y]=x;
return 1;
}
}
}
return 0;
}
int ans[N];
void KM(){
for(int x=1;x<=n;x++){
la[x]=-INF;
for(int y=1;y<=n;y++){
la[x]=max(la[x],w[x][y]);
}
}
for(int x=1;x<=n;x++){
while(1){
memset(va,0,sizeof(va));
memset(vb,0,sizeof(vb));
if(dfs(x))break;
delta=INF;
for(int i=1;i<=n;i++)
if(va[i])
for(int j=1;j<=n;j++){
if(!vb[j])
delta=min(delta,la[i]+lb[j]-w[i][j]);
}
for(int i=1;i<=n;i++){
if(va[i])la[i]-=delta;
if(vb[i])lb[i]+=delta;
}
}
}
for(int y=1;y<=n;y++){
ans[match[y]]=y;
}
return;
}
struct point{
int x,y;
}black[N],white[N];
double dis(point a,point b){
return sqrt((b.x-a.x)*(b.x-a.x)*1.0+(b.y-a.y)*(b.y-a.y)*1.0);
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
int x,y;
scanf("%d%d",&x,&y);
black[i].x=x,black[i].y=y;
}
for(int i=1;i<=n;i++){
int x,y;
scanf("%d%d",&x,&y);
white[i].x=x,white[i].y=y;
}
for(int x=1;x<=n;x++)
for(int y=1;y<=n;y++){
w[x][y]=-dis(black[x],white[y]);
}
KM();
for(int x=1;x<=n;x++)
printf("%d\n",ans[x]);
return 0;
}
dalao,为什么在dfs时求delta就会超时啊?不应该是等价的吗?
常数大
大佬,你说既然是double就不能使用常见的delta了,因为能更新delta不代表是最终结果.这是什么意思啊
抱歉,之前写错了,实际上只会TLE