|
|||||||
|
Network Capacity
A city network consists of N (0 < N <= 100) nodes successively numbered from 1 to N, and one-way direct connections between nodes. There exist at most two direct connections between any two nodes k and l: at most one from k to l and at most one from l to k. Every direct connection has fixed capacity, being a natural number from the interval [1, 32000]. A nonempty sequence of distinct direct connections is called a route from a node k to l, if:
The capacity of a route is equal to the minimal capacity of direct connections it comprises. There may exist many routes of different capacity between two network nodes. There may be no route too. TaskWrite a program, that reads from the text file PRZ.IN data on a city network. Next, it computes answers to queries read from PRZ.IN - each of which is in a form of a pair of numbers k l denoting two distinct nodes. Then it writes the answers in consecutive lines of the text file PRZ.OUT, and each answer is:
The data in the text file PRZ.IN is written in the following form: The number of nodes N is written in the first line. It is followed by N successive lines each with descriptions of direct connections beginning at successive network nodes (in the i-th of these lines there are connections beginning in the node i). The N+1 lines are followed by a nonempty sequence of queries and the end of the file. A description of direct connections beginning at a specified network node k is a sequence of nonnegative integers separated by single spaces. The first element of the sequence is the number nck of those connections. If nck = 0, then the sequence ends, if not then there follow nck descriptions of every of the connections in a form of a pair of numbers. The former is the number of node the connection leads to, the latter is its capacity. Immediately after the last number of each description of direct connections there is a semicolon followed by the end of the line. Every query has a form of a pair of node numbers, i.e. numbers in the interval [1, 100]. All the queries form a sequence (of even length) of natural numbers separated by a space or a single end-of-line character. The last number is directly followed by the end of the file. The data in the file PRZ.IN is written faultlessly and your program needs not examine this. The answers should be written to the file PRZ.OUT, in the order corresponding to the order of queries, in a form of a sequence of nonnegative numbers separated by a single end-of-line characters. The last answer should be directly followed by the end of the file. ExampleFor the file PRZ.IN: 5 3 2 3 3 2 5 1; 1 3 1; 1 2 1; 2 3 2 5 4; 1 4 3; 1 4 4 1 2 3 3 4 1 5 5 2 2 4 4 5 3 4 4 2(end of file)your program should create the following file PRZ.OUT: 1 0 1 0 1 1 0 4 0 1(end of file) At the beginning of your program, in a comment, give your last and first name, and the number of your working stand. Your program should look for the file PRZ.IN in the current directory and create the file PRZ.OUT also in the current directory. The source file containing the program written by you should be named PRZ.???, where ??? are substituted by at most three-letter abbreviation of the programming language used. The same program in an executable form should be written in a file PRZ.EXE. Both the files should be stored on a hard disk and on a floppy disk. The solution to the problem consists of a program - only one - in a source and executable form, stored, satisfying the above rules, on a hard disk and on a floppy disk, and of the description of your algorithm and the justification of its correctness. |