10

我承认这是我的功课。任务声明说我必须编写一个程序来查找将由标准输入输入的图的拓扑顺序。然后我需要提交它以在教授的服务器上评分。

现在不是算法问题。这更像是一个技术问题。在我的计算机中，我使用 .NET 编译器 (csc)，而教授的评分机使用某种形式的单声道。

它运作良好，直到评分员说我得到 30/100。我的一个朋友建议我使用评分器的“手动输入系统”，所以我开始了，我让它为邻接列表创建了 100000 个列表的数组。

几秒钟后，评分员报告说我的程序崩溃了。

Stacktrace:

at (wrapper managed-to-native) object.__icall_wrapper_mono_object_new_fast (intptr) <0x00004>
at (wrapper managed-to-native) object.__icall_wrapper_mono_object_new_fast (intptr) <0xffffffff>
at System.Exception.ToString () <0x00026>
at (wrapper runtime-invoke) object.runtime_invoke_object__this__ (object,intptr,intptr,intptr) <0xffffffff>
at (wrapper managed-to-native) object.__icall_wrapper_mono_object_new_fast (intptr) <0x00004>
at (wrapper managed-to-native) object.__icall_wrapper_mono_object_new_fast (intptr) <0xffffffff>
at System.Exception.ToString () <0x00026>
at (wrapper runtime-invoke) object.runtime_invoke_object__this__ (object,intptr,intptr,intptr) <0xffffffff>
at (wrapper managed-to-native) object.__icall_wrapper_mono_object_new_fast (intptr) <0x00004>
at (wrapper managed-to-native) object.__icall_wrapper_mono_object_new_fast (intptr) <0xffffffff>
at System.Exception.ToString () <0x00026>
at (wrapper runtime-invoke) object.runtime_invoke_object__this__ (object,intptr,intptr,intptr) <0xffffffff>
at (wrapper managed-to-native) object.__icall_wrapper_mono_object_new_fast (intptr) <0x00004>
at (wrapper managed-to-native) object.__icall_wrapper_mono_object_new_fast (intptr) <0xffffffff>
at System.Exception.ToString () <0x00026>
at (wrapper runtime-invoke) object.runtime_invoke_object__this__ (object,intptr,intptr,intptr) <0xffffffff>
at (wrapper managed-to-native) object.__icall_wrapper_mono_object_new_fast (intptr) <0x00004>
at (wrapper managed-to-native) object.__icall_wrapper_mono_object_new_fast (intptr) <0xffffffff>
at System.Exception.ToString () <0x00026>
at (wrapper runtime-invoke) object.runtime_invoke_object__this__ (object,intptr,intptr,intptr) <0xffffffff>
at (wrapper managed-to-native) object.__icall_wrapper_mono_object_new_fast (intptr) <0x00004>
at (wrapper managed-to-native) object.__icall_wrapper_mono_object_new_fast (intptr) <0xffffffff>
at System.Exception.ToString () <0x00026>
at (wrapper runtime-invoke) object.runtime_invoke

这对我来说有点奇怪和不安，但我还没有找到答案。同样，这个程序在我的电脑上运行得很好。

这是我的程序的一部分：

using System;
using System.Collections;
using System.Collections.Generic;

class topo{
public static void Main(){
    string[] ST = Console.ReadLine().Split(' ');
    int N=Convert.ToInt32(ST[0]), M=Convert.ToInt32(ST[1]);
    int[] ins = new int[N];  //node's total in-degrees
    List<int>[] E = new List<int>[N];

    for(int n=0;n<N;n++)    
        E[n] = new List<int>();

    for(int m=0;m<M;m++){
        ST = Console.ReadLine().Split(' ');
        int u = Convert.ToInt32(ST[0]);
        int v = Convert.ToInt32(ST[1]);
        E[u-1].Add(v-1);
        ins[v-1]++;
    }

    Queue S = new Queue();
    List<int> L = new List<int>(); //result list

    for(int n=0;n<N;n++){
        //add stranded nodes directly and don't process it
        if(ins[n]==0 && E[n].Count==0)
            L.Add(n);

        //put into queue
        else if(ins[n]==0)
            S.Enqueue(n);
    }

    while(S.Count>0){
        int n = (int) S.Dequeue();
        L.Add(n);
        foreach(int m in E[n])
            if(--ins[m]==0)
                S.Enqueue(m);
    }

    foreach(int n in L)
        Console.WriteLine(n+1);

}

}

非常感谢您，我感谢您的每一个回复。

编辑：我再次查看了评分者的输出，看看我是否遗漏了什么，确实我做到了。它说“syscal：2”，但我只知道“程序没有正常退出”。

编辑#2：我尝试让程序尝试制作各种大小的列表数组，范围从 5000、10000 等，在 40000 之后，“手动输入系统”说程序得到了 System.OutOfMemoryException。进一步研究允许学生进入的评分器的各个部分，似乎教授错误地配置了他的评分参数并且给我们的记忆比宣布的要少。（他说“32MB”，但程序在大约 16MB 时崩溃）

我已经向他报告了这个错误，他（现在）正在调查它。

4

2 回答 2

2

u如果or的值v小于 1 ，则以下代码将失败。

for(int m=0;m<M;m++){
    ST = Console.ReadLine().Split(' ');
    int u = Convert.ToInt32(ST[0]);
    int v = Convert.ToInt32(ST[1]);
    E[u-1].Add(v-1);
    ins[v-1]++;
}

因为u-1orv-1将是负数，这将引发异常。

于 2011-03-12T20:29:15.260 回答
0

跟进：这是轶事，自我回答，而且很晚，因为我刚刚意识到可以回答自己。后来我被告知我超过了评分系统强制执行的内存限制。然而，在我的案例中，这个例外非常神秘，并且评分者没有报告这个问题。（它只将我标记为不正确。）

我也很粗心，没有意识到较小的输入有效，这就是为什么我得到 30/100 而不是零分的原因。

对于未来的读者：在自动评分器环境中编程时，请确保您的程序没有超出内存限制，内存限制可能存在但您可能不知道（即未写在问题陈述中）。

于 2014-11-13T07:44:03.273 回答