POJ 1789 下的有关问题，求解.

POJ 1789 上的问题，求解.......

今天我看到poj上的1789这道题目，是个最小生成树问题，开始我用prim做，提交了n次，没通过，实在没找出错误在哪，
但每次都是“return error”，那时我是真的无语了，后来我把那些变量改成全局变量，嘿，他居然通过了。
这是怎么回事？？？？

在poj上返回“return error”是超时把，把变量弄成全局变量能节省时间吗？？？？
没改之前的代码：

C/C++ code


#include<iostream>
using namespace std;
int f(char*a,char*b)
{
    int sun=0,k;
    for( k=0;k<7;k++)
        if(a[k]!=b[k]!=0)sun++;
    return sun;
}
void prim(char str[][7],int t)
{
    int i,j,k;
    int a[2000][2000]={0};
    for(i=0;i<t;i++)
        for(j=i;j<t;j++)
            a[i][j]=a[j][i]=f(str[i],str[j]);
    int quan[2000];
    bool v[2000];
    v[0]=1;
    for(i=1;i<t;i++)
    {
        quan[i]=a[0][i];
        v[i]=0;
    }
    int sum=0;
    for(i=1;i<t;i++)
    {
        int j,min=8;
        for( k=1;k<t;k++)
            if(min>quan[k]&&!v[k]){min=quan[k];j=k;}
        v[j]=1;
        sum+=min;
        for(k=1;k<t;k++)
            if(quan[k]>a[j][k]&&!v[k]){quan[k]=a[j][k];}
    }
    cout<<"The highest possible quality is 1/"<<sum<<'.'<<endl;
}

int main()
{
    char str[2000][7];
    int t,i;
    while(cin>>t&&t)
    {
        for( i=0;i<t;i++)
            cin>>str[i];
        prim(str,t);
    }
    return 0;
}

改之后的代码：

C/C++ code


#include<iostream>
using namespace std;
char str[2000][7];
int a[2000][2000];
int quan[2000];
bool v[2000];
int t;
int f(char*a,char*b)
{
    int sun=0,k;
    for( k=0;k<7;k++)
        if(a[k]!=b[k]!=0)sun++;
    return sun;
}
void prim()
{
    int i,j,k;
    for(i=0;i<t;i++)
        for(j=i;j<t;j++)
            a[i][j]=a[j][i]=f(str[i],str[j]);
    v[0]=1;
    for(i=1;i<t;i++)
    {
        quan[i]=a[0][i];
        v[i]=0;
    }
    int sum=0;
    for(i=1;i<t;i++)
    {
        int j,min=8;
        for( k=1;k<t;k++)
            if(min>quan[k]&&!v[k]){min=quan[k];j=k;}
        v[j]=1;
        sum+=min;
        for(k=1;k<t;k++)
            if(quan[k]>a[j][k]&&!v[k]){quan[k]=a[j][k];}
    }
    cout<<"The highest possible quality is 1/"<<sum<<'.'<<endl;
}

int main()
{
    int i;
    while(cin>>t&&t)
    {
        for( i=0;i<t;i++)
            cin>>str[i];
        prim();
    }
    return 0;
}

------解决方案--------------------
这个应该是内存超出，函数中的局部变量开二维数组2000*2000实在是有些大了，结果就报错了。
全局变量的2000*2000还是在可以承受的范围内的
------解决方案--------------------
Runtime Error (RE) : 运行时错误，这个一般是程序在运行期间执行了非法的操作造成的。
超时错误是 Time Limit Exceeded 个吧！！！
------解决方案--------------------
我还是建议你把数组换成vector，这样可以动态增加
------解决方案--------------------
明显栈溢出，在函数中直接定义的数组是在栈区中申请空间，栈空间是有限的（当然你可以自己开大栈区）
如果是在函数外面定义，那么是在堆中申请，所以大数组需要在函数外面定义
像下面这样可以开大栈区，当然一般情况下用不到，如果你觉得有些题目递归深度很深的话，最后加上

C/C++ code


#include<iostream>
#include<cstring>
using namespace std;
#pragma comment(linker,"/STACK:102400000,102400000") //开大栈区
int main(){
 
    cout<<"hello world"<<endl;
 
    return 0;
}

POJ 1789 下的有关问题，求解.

相关推荐