Pro.ID22258 TitleMinimum Spanning Tree Title链接http://10.20.2.8/oj/exercise/problem?problem_id=22258 AC0 Submit0 Ratio- 时间&空间限制描述Given graph G which is a connected, weighted, undirected graph, a spanning tree T is a subgraph of G which is: (1) a tree that (2) connects all the vertices of G together. The weight of a spanning tree is the sum of the weights of the edges in that tree. A minimum spanning tree is a spanning tree: (3) whose weight is less than or equal to the weight of every other spanning tree. Write a program that determines if a given tree T is a Minimum Spanning Tree for a given graph G. 输入Your program will be tested on one or more test cases. For each test case you’ll be given a graph G and one or more trees to test. The first line of a test case will have a single positive integer n denoting the number of vertices in G (where 1 < n ≤ 1000). The vertices are numbered starting from 1. The next (n−1) lines specify the upper triangle of the graph’s adjacency matrix as seen here: W1,2 W1,3 . . . W1,n−1 W1,n where Wi,j is the weight of the edge between vertices i and j. Wi,j = 0 iff there is no edge between i and j. Note that 0 ≤ Wi,j ≤ 1000 ( R T1 T2 . . . Tc ) where R is the number of the vertex at the root and T1, . . . , Tc (where 0 < c ≤ 1000) are the sub-trees of R specified recursively. 输出Description Given graph G which is a connected, weighted, undirected graph, a spanning tree T is a subgraph of G which is: (1) a tree that (2) connects all the vertices of G together. The weight of a spanning tree is the sum of the weights of the edges in that tree. A minimum spanning tree is a spanning tree: (3) whose weight is less than or equal to the weight of every other spanning tree. Write a program that determines if a given tree T is a Minimum Spanning Tree for a given graph G. Input Your program will be tested on one or more test cases. For each test case you’ll be given a graph G and one or more trees to test. The first line of a test case will have a single positive integer n denoting the number of vertices in G (where 1 < n ≤ 1000). The vertices are numbered starting from 1. The next (n−1) lines specify the upper triangle of the graph’s adjacency matrix as seen here: W1,2 W1,3 . . . W1,n−1 W1,n where Wi,j is the weight of the edge between vertices i and j. Wi,j = 0 iff there is no edge between i and j. Note that 0 ≤ Wi,j ≤ 1000 ( R T1 T2 . . . Tc ) where R is the number of the vertex at the root and T1, . . . , Tc (where 0 < c ≤ 1000) are the sub-trees of R specified recursively. Output For each query, write the result on a separate line using the following format: a.b. result where a is the test case number (starting at 1,) and b is the query number within this test case (again starting at 1.) result is either "YES" or "NO" indicating if the tree is a minimum spanning tree or not. Sample Input 6 2 6 11 0 0 0 10 0 0 0 0 7 3 4 5 3 (6 (3 (1 2)) (4 5)) (3 (1 2) (6 (4 5))) (4 1 2 5 6) 5 6 6 0 6 6 0 10 10 6 10 2 (1 2 5 (3 4)) (5 4 (3 2 1)) 0 Sample Output 1.1 YES 1.2 YES 1.3 NO 2.1 YES 2.2 YES Hint The following figures illustrate the sample I/O. The top half is for the first test case, while the second test case is on the bottom. In the graph, vertex numbers are underlined and the edges of a minimum spanning tree are drawn in thicker lines.
题中的 iff 是“当且仅当”。 Source 样例输入6 2 6 11 0 0 0 10 0 0 0 0 7 3 4 5 3 (6 (3 (1 2)) (4 5)) (3 (1 2) (6 (4 5))) (4 1 2 5 6) 5 6 6 0 6 6 0 10 10 6 10 2 (1 2 5 (3 4)) (5 4 (3 2 1)) 0 样例输出1.1 YES 1.2 YES 1.3 NO 2.1 YES 2.2 YES 提示The following figures illustrate the sample I/O. The top half is for the first test case, while the second test case is on the bottom. In the graph, vertex numbers are underlined and the edges of a minimum spanning tree are drawn in thicker lines.
题中的 iff 是“当且仅当”。 |
|Archiver|手机版|小黑屋|同和创作矩阵
( 粤ICP备20019636号-1 )
GMT+8, 2025-2-4 18:59 , Processed in 0.014986 second(s), 14 queries .
Powered by Discuz! X3.4 Licensed
© 2001-2017 Comsenz Inc.
