描述
外星人逐渐逼近，为了保护地球，现在决定直接在外空进行战斗。 现在我们有N个导弹。需要在最短的时间内，用这N个导弹摧毁敌方n个目标(1个导弹只能摧毁1个目标)。N个导弹和目标的位置不一定相同，但是给每个导弹确定目标是一件很麻烦的事情。请你编程帮助给每个导弹确定目标，使每个导弹到其目标的距离之和最小。
格式
输入格式
第一行输入N(N<=20) 接下来N行每行包含一个坐标(x,y)，表示一个导弹，-10000
输出格式
每个导弹到其目标距离之和的最小值。结果保留3位小数。
代码
#include <cstdio>
#include <cstring>
#include <cmath>
#define INF 0x3f
#define maxn 25
using namespace std;
struct Po{
int x,y;
Po(
int x=
0,
int y=
0){
this->x=x;
this->y=y;
}
};
int nx,ny,linky[maxn];
double lack,w[maxn][maxn],lx[maxn],ly[maxn];
bool visx[maxn],visy[maxn];
int n;
Po mi[maxn],tar[maxn];
double dist(Po x,Po y){
return sqrt(
pow(x.x-y.x,
2.0)+
pow(x.y-y.y,
2.0));
}
bool find(
int x){
visx[x]=
true;
for(
int i=
1;i<=ny;i++){
if(visy[i])
continue;
double t=lx[x]+ly[i]-w[x][i];
if(t<
1e-5){
visy[i]=
true;
if(linky[i]==-
1||find(linky[i])){
linky[i]=x;
return true;
}
}
else if(t<lack-
1e-5) lack=t;
}
return false;
}
double KM(){
memset(linky,-
1,
sizeof(linky));
for(
int i=
1;i<=ny;i++) ly[i]=
0.000;
for(
int i=
1;i<=nx;i++){
lx[i]=INF;
for(
int j=
1;j<=ny;j++)
if(w[i][j]-
1e-5>lx[i]) lx[i]=w[i][j];
}
for(
int x=
1;x<=nx;x++){
while(
true){
memset(visx,
0,
sizeof(visx));
memset(visy,
0,
sizeof(visy));
lack=INF;
if(find(x))
break;
for(
int i=
1;i<=ny;i++){
if(visx[i]) lx[i]-=lack;
if(visy[i]) ly[i]+=lack;
}
}
}
double ans=
0.000;
for(
int i=
1;i<=ny;i++)
ans-=w[linky[i]][i];
return ans;
}
int main(){
scanf(
"%d",&n); nx=ny=n;
for(
int i=
1;i<=n;i++)
scanf(
"%d%d",&mi[i].x,&mi[i].y);
for(
int i=
1;i<=n;i++)
scanf(
"%d%d",&tar[i].x,&tar[i].y);
for(
int i=
1;i<=n;i++)
for(
int j=
1;j<=n;j++)
w[i][j]=-dist(mi[i],tar[j]);
printf(
"%.3f",KM());
return 0;
}
转载于:https://www.cnblogs.com/leotan0321/p/6081395.html
