首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 软件管理 > 软件架构设计 >

一道ACM题目总是AC不了,求指出异常。

2013-11-15 
一道ACM题目总是AC不了,求指出错误。。http://uva.onlinejudge.org/index.php?optioncom_onlinejudge&Itemi

一道ACM题目总是AC不了,求指出错误。。
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=108&problem=152&mosmsg=Submission+received+with+ID+12668984
一道搜索题可以回溯也可以暴力枚举,我用的是暴力枚举,总是WA,样例都通过了,就是找不到原因,求大神指出错误,谢谢啦。

#include<iostream>
#include<algorithm>
#include<iomanip>
#include<cstring>
#include<cmath>

using namespace std;

int num[10];
int num1[10];

class P
{
public:
    int x,y;
}point[10];

double dis(int len)
{
    double sum=0;
    for(int i=1;i<len;i++)
    {
        sum=sum+sqrt((point[num[i]].x-point[num[i-1]].x)*(point[num[i]].x-point[num[i-1]].x)+(point[num[i]].y-point[num[i-1]].y)*(point[num[i]].y-point[num[i-1]].y))+16;
    }
    return sum;
}

int main()
{
    int n,k=0;
    while(cin>>n&&n)
    {
        memset(point,0,sizeof(point));
        memset(num,0,sizeof(num));
        memset(num1,0,sizeof(num1));
        int i,j;
        for(i=0;i<n;i++)
            cin>>point[i].x>>point[i].y;
        for(i=0;i<n;i++)
            num[i]=i;
        double minlen=dis(n);
        while(next_permutation(num,num+n))
        {
            if(dis(n)<minlen)
            {
                memcpy(num1,num,sizeof(num));
                minlen=dis(n);
            }
        }
        cout<<"**********************************************************"<<endl;
        cout<<"Network #"<<++k<<endl;
        for(i=1;i<n;i++)
        {
            double d=sqrt((point[num1[i]].x-point[num1[i-1]].x)*(point[num1[i]].x-point[num1[i-1]].x)+(point[num1[i]].y-point[num1[i-1]].y)*(point[num1[i]].y-point[num1[i-1]].y));
            cout<<"Cable requirement to connect ("<<point[num1[i-1]].x<<","<<point[num1[i-1]].y<<") to ("<<point[num1[i]].x<<","<<point[num1[i]].y<<") is ";
            cout<<fixed<<setprecision(2)<<d+16<<" feet."<<endl;
        }
        cout<<"Number of feet of cable required is "<<fixed<<setprecision(2)<<minlen<<"."<<endl;
    }
    return 0;
}
ACM 回溯
[解决办法]
如果初始解是最优解的话你的num1全是0

热点排行