求助WA 自己下载的数据能过

#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 条评论

  • @ 2015-11-27 03:13:29

    请问您写的是c还是c++?
    如果是c++,则printf下double的标准输出是“%.3f”的,而不是"%.3lf"。只有scanf读入的时候double才是"%lf"的。

  • 1

信息

ID
1228
难度
7
分类
图结构 | 二分图 点击显示
标签
(无)
递交数
710
已通过
151
通过率
21%
被复制
4
上传者