hdu 1875 WA 检查不出来...求助!
答案:1 悬赏:0
解决时间 2021-02-28 08:45
- 提问者网友:血樱陌殇
- 2021-02-27 13:47
http://acm.hdu.edu.cn/showproblem.php?pid=1875
#include
#include
#include
int a[101];
struct ROAD
{
int num1,num2;
double len;
}road[5051];
int cmp(const void *a,const void *b)
{
return (*(struct ROAD *)a).len - (*(struct ROAD *)b).len;
}
double combine(int x,int y,double len)
{
while(x!=a[x])
x=a[x];
while(y!=a[y])
y=a[y];
if(x==y)return 0;
a[y]=x;
return len*100;
}
int main()
{
int t,n,i,j,m,b[101][2],d;
double sum;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(i=1;i<=n;i++)
a[i]=i;
for(i=1;i<=n;i++)
scanf("%d%d",&b[i][0],&b[i][1]);
for(d=0,i=1;i {
for(j=i+1;j<=n;j++)
{
road[d].num1=i;
road[d].num2=j;
road[d].len=sqrt(pow((b[i][0]-b[j][0]),2)+pow((b[i][1]-b[j][1]),2));
d++;
}
}
qsort(road,d,sizeof(road[0]),cmp);
for(sum=0,i=0;i {
if(road[i].len>=10&&road[i].len<=1000)
{
sum+=combine(road[i].num1,road[i].num2,road[i].len);
}
}
for(d=0,i=1;i<=n;i++)
{
if(a[i]==i)d++;
}
if(d>1)printf("oh!\n");
else printf("%.1lf\n",sum);
}
}
麻烦了,先谢谢~
int cmp(const void *a,const void *b)改成double cmp(const void *a,const void *b)了
但还是超时。为什么呢?怎么改呀?
最佳答案
- 二级知识专家网友:情战凌云蔡小葵
- 2021-02-27 15:23
楼主排序法则写的不对。。
排序法则不能返回 浮点数。。。
如果你用返回int型会被强制转换。。
没用过C语言的qsort函数 所以不会改。。
我用C++的sort函数排了下序 就过了。。
楼看着自己改改把。。。
AC code
。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
#include
#include
#include
using namespace std;
int a[101];
struct ROAD
{
int num1,num2;
double len;
}road[5051];
int cmp(struct ROAD a,struct ROAD b)
{
return a.len
}
double combine(int x,int y,double len)
{
while(x!=a[x])
x=a[x];
while(y!=a[y])
y=a[y];
if(x==y)return 0;
a[y]=x;
return len*100;
}
int main()
{
int t,n,i,j,b[101][2],d;
double sum;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(i=1;i<=n;i++)
a[i]=i;
for(i=1;i<=n;i++)
scanf("%d%d",&b[i][0],&b[i][1]);
for(d=0,i=1;i
{
for(j=i+1;j<=n;j++)
{
road[d].num1=i;
road[d].num2=j;
road[d].len=sqrt(pow((b[i][0]-b[j][0]),2)+pow((b[i][1]-b[j][1]),2));
d++;
}
}
sort(road,road+d,cmp);
for(sum=0,i=0;i
{
if(road[i].len>=10&&road[i].len<=1000)
{
sum+=combine(road[i].num1,road[i].num2,road[i].len);
}
}
for(d=0,i=1;i<=n;i++)
{
if(a[i]==i)d++;
}
if(d>1)printf("oh!\n");
else printf("%.1lf\n",sum);
}
return 0;
}
我要举报
大家都在看
推荐资讯