20220429ACM练习题.docx

20220429ACM练习题 20220429ACM练习题~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 10100 Longest Paths~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~It is a well known fact that some people do not have their social abilities completely enabled. One example is the lack of talent for calculating distances and intervals of time. This causes some people to always choose the longest way to go from one place to another, with the consequence that they are late to whatever appointments they have, including weddings and programming contests. This can be highly annoying for their friends.César has this kind of problem. When he has to go from one point toanother he realizes that he has to visit many people, and thus always chooses the longest path. One of César's friends, Felipe, has understood the nature of the problem. Felipe thinks that with the help of a computer he might be able to calculate the time that César is going to need to arrive to his destination. That way he could spend his time in something more enjoyable than waiting for César.Your goal is to help Felipe developing a program that computes the length of the longest path that can be constructed in a given graph from a given starting point (César's residence). You can assume that the graph has no cycles (there is no path from any node to itself), so César will reach his destination in a finite time. In the same line of reasoning, nodes are not considered directly connected to themselves. InputThe input consists of a number of cases. The first line on each case contains a positive number n ( ) that specifies the number of points that César might visit (i.e., the number of nodes in the graph).A value of n = 0 indicates the end of the input.After this, a second number s is provided, indicating the starting point in César's journey (). Then, you are given a list of pairs of places p andq, one pair per line, with the places on each line separated by white-space. The pair ``\sar can visit q after p. A pair of zeros (``0 0\As mentioned before, you can assume that the graphs provided will not be cyclic. OutputFor each test case you have to find the length of the longest path that begins at the starting place. You also have to print the number of the final place of such longest path. If there are several paths of maximum length, print the final place with smallest number.Print a new line after each test case. Sample Input 2 1 1 2 0 0 5 3 1 2 3 5 3 1 2 4 4 5 0 0 5 5 5 1 5 2 5 3 5 4 4 1 4 2 0 0 0Sample OutputCase 1: The longest path from 1 has length 1, finishing at 2. Case 2: The longest path from 3 has length 4, finishing at 5. Case 3: The longest path from 5 has length 2, finishing at 1.//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 10104 Bicoloring~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~In 1976 the ``Four Color Map Theorem\of a computer. This theorem states that every map can be colored using only four colors, in such a way that no region is colored using the same color as a neighbor region.Here you are asked to solve a simpler similar problem. You have to decide whether a given arbitrary connected graph can be bicolored. That is, if one can assign colors (from a palette of two) to the nodes in such a way thatno two adjacent nodes have the same color. To simplify the problem you can assume:? no node will have an edge to itself.? the graph is nondirected. That is, if a node a is said to be connected to a node b, then you must assume that b is connected to a.? the graph will be strongly connected. That is, there will be at least one path from any node to any other node. InputThe input consists of several test cases. Each test case starts with a line containing the number n ( 1 < n < 200) of different nodes. The second line contains the number of edges l. After this, l lines will follow, each containing two numbers that specify an edge between the two nodes that they represent. A node in the graph will be labeled using a number a ( ). An input with n = 0 will mark the end of the input and is not to be processed. OutputYou have to decide whether the input graph can be bicolored or not, and print it as shown below. Sample Input 3 3 0 1 1 2 2 0 9 8 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0Sample Output NOT BICOLORABLE. BICOLORABLE.//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////。