- 拯救世界-星际大战
- 2015-11-26 19:55:51 @
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=24;
struct Point
{
int x, y;
void read()
{
scanf("%d%d",&x,&y);
}
}A[maxn],B[maxn];
int n,za[maxn],zb[maxn],matcha[maxn],matchb[maxn];
double G[maxn][maxn],la[maxn],lb[maxn];
double sqr(double x){return x*x;}
double dist(Point a,Point b)
{
return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));
}
bool DFS(int u)
{
za[u]=1;
for (int v=1;v<=n;v++)
{
if (zb[v]||la[u]+lb[v]!=G[u][v]) continue;
zb[v]=1;
if (!matchb[v]||DFS(matchb[v]))
{
matchb[v]=u;
matcha[u]=v;
return true;
}
}
return false;
}
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++) A[i].read();
for (int i=1;i<=n;i++) B[i].read();
for (int i=1;i<=n;i++)
{
la[i]=0,lb[i]=0;
for (int j=1;j<=n;j++)
G[i][j]=1e5-dist(A[i],B[j]),
la[i]=max(la[i],G[i][j]);
}
for (int k=1;k<=n;k++)
while (1)
{
memset(za,0,sizeof za);
memset(zb,0,sizeof zb);
if (DFS(k)) break;
double d=1e10;
for (int i=1;i<=n;i++) if (za[i])
for (int j=1;j<=n;j++) if (!zb[j])
d=min(d,la[i]+lb[j]-G[i][j]);
for (int i=1;i<=n;i++)
{
if (za[i]) la[i]-=d;
if (zb[i]) lb[i]+=d;
}
}
double ans=0;
for (int i=1;i<=n;i++) ans+=1e5-G[matchb[i]][i];
printf("%.3lf\n",ans);
return 0;
}
1 条评论
-
少女夜夜 LV 9 MOD @ 2015-11-27 03:13:29
请问您写的是c还是c++?
如果是c++,则printf下double的标准输出是“%.3f”的,而不是"%.3lf"。只有scanf读入的时候double才是"%lf"的。
- 1