时间:2008-08-28 06:00:56   来源:论坛整理  作者:  编辑:chinaitzhe

题目要求为:
The Graph
The graph will be a connected weighted undirected graph, with at least 1 vertex, and at most 100000 vertices. Vertices will be numbered 0, 1, 2, ... V – 1, for a graph with V vertices. There will be at most 1000000 edges. Edge weights will be positive integers, each at least 1, and less than 1000000. The union and find operations must be implemented using the data structures as required below, the input read as required below, and the output produced as required below. (The input will be correct, and no extra marks will be given for handling incorrect input.)
Testing
Programs will be tested automatically on alacritas / lawson, marks for each test will be awarded on a pass/fail basis. Example input and output files are provided in the assignment2 directories on alacritas and lawson.
Data Structure Requirements
In this assignment the union and find operations must be implemented using the array and linked list based data structures described briefly in the lectures and on page 265 of the prescribed textbook (where they are described as the basis for implementing the operations with a O(M N log N) running time for M finds and N unions). Attaining a conceptual level understanding of the use of the data structures in the implementation of the operations should be a significant part of your work in doing this assignment.
The array that is used for the find operation must be an array of 100000 ints, e.g.:
int find_array[100000]; (For a graph of V vertices only find_array[0] to find_array[V-1] are to be used.)
The linked lists that are used to store the set information must be dummy header linked lists of the following type (as used in the weekly work):
typedef struct node *node_ptr;
struct node
{
int data_item;
node_ptr next;
}; Each header node's data_item must contain the number of items in the set, and the data_items of the other nodes in the linked list must contain the vertex numbers of the vertices in the set. The sets must be in an array of 100000 node_ptrs, e.g.: node_ptr sets[100000]; (For a graph of V vertices only sets[0] to sets[V-1] are to be used.)
Notes on the O() Running Time Requirements
a) You can assume that each call to any of scanf, printf, malloc and free, takes time that is O(1).
b) Although E and V are actually limited, the existence of these limits must be ignored for the purposes of the O() running time requirements.
c) You do not need to make any special effort to have good constants in the running time of your code, but equally, you must not make any effort to make it excessively inefficient in constant terms – the marker will limit the length of time for which they wait for a test to complete.
Input and Output
Input must be read with scanf and output written with printf. The input will contain only what is described here, e.g. there will be no blank spaces other than those mentioned. The output must contain only what is described here.
The input will start with a line containing two integers separated by a space. The first integer is the number of vertices. The second integer is the number of edges. (The number of edges is needed for the challenge level assignment, but in the standard level assignment it could be ignored after it has been read.)
Then, there will be a series of lines, one per edge. Each such line will contain three integers, with a space between the first and second, and a space between the second and third. The first integer will be the weight of the edge. The second integer will be the lower numbered of the vertices at the ends of the edge. The third integer will be the higher numbered of the vertices at the ends of the edge.
In the standard level assignment, the edges will be given in the order in which the edges must be considered for addition to the solution. (The edges must be considered in nondecreasing order of weight. Edges of the same weight must be considered in nondecreasing order of lower numbered vertex. Edges of the same weight and lower numbered vertex must be considered in increasing order of higher numbered vertex.)
The output must contain only the edges in the minimal spanning tree. The edges must be in the order in which they had to be considered for addition to the solution, each on a separate line containing the same as the input line describing the edge.
Note that in the standard level assignment it is possible to read an edge, and at that point determine whether it is in the solution and must be printed, so it is not necessary to store edges


我的qq是:77373996

能做出来的请留下联系方式,谢谢

网友回复:不懂，关注下
网友回复:数据结构中比较难的图问题，得花时间好好想想~~
网友回复:求最小生成树？
网友回复:很多算法和数据结构里面都有，
可以照着写。
网友回复:这不就是个有向图的问题吗...
网友回复:瞄了一下，数据结构里面的东西
网友回复:英语看不懂啊啊 啊
网友回复:
Example input and output files are provided in the assignment2 directories on alacritas and lawson.

缺少测试样本数据。