UVa 196

Ordering Tasks

from Volume 2. Data Structures :: Graphs

Description

输入一张电子表格，请你把单元格填上的函数计算出来，填上数字输出。函数的形式都是，其他单元格上的数字相加，并且保证没有求不出来的函数。

Solution

把单元格当作点，单元格之间的关系当作边，变成一张图。这题的求解就变成了，去遍历一张图的每一个点，而函数单元格要在其参数走到之后才能走到。所以拓扑排序，或者是暴力什么的，都可以。但是要注意，虽然不知道测试数据怎么样，但是题目的数据规模有点吓人，是1000 * 1000的点。如此多的点无法用一张邻接表来存储，需要把函数单元格映射到链表上，用链表来存储图的边。这题的难点就是在输入表格的时候，如何用二维数组映射链表来存储（其实就是广义表）。不过简单的地方就是，OJ上好似没有特别恶心的测试点（POJ上甚至明显WA的代码都可能AC）。