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;} 

 

查看更多 下一篇