男人八题解题报告

[ADN.cn][Library]Solutions 做男人不容易系列Solutions Amber 第 1 页 共 15 页 做男人不容易系列 Solu tions Amber 2 years ago, I trained in Fudan University in Shanghai and attended this contest hold by Lou Tiancheng. The title of this contest is “ hard to be a man” and the subtitle is “ If you are a man, pass all 8 problems” . I got only 1 problem accepted at that time. Actually, no one can be “ a man” except LTC himself at that time. Now there is still only 3 guys who finished all problems except the problemsetter LTC. They are timgreen, geworm, Savior. How I admire them! Well, I decide to be a man before my 18th birthday. For my foreign friends, I decide to write the English version in the description and the solution with my poor English. [ADN.cn][Library]Solutions 做男人不容易系列Solutions Amber 第 2 页 共 15 页 Problem A (POJ 1737): Connected Graph [Description] Find the number of connected labeled undirected graphs with n nodes. 找出有标号的n 个点的无向连通图的个数. [Solution] If we do not considered whether the graph is connected, there exists 2^C(n, 2) graphs in total. Let G(n) = 2^C(n, 2). If we know the number of unconnected ones, we will know the answer indirectly. Let F(n) is the answer. Consider the connected component C that contains node 1 and with the size k, namely |C| = k. Because C is unconnected, k < n. So there exists C(n – 1, k - 1) ways to choose another k - 1 nodes to make up connected component C. So there exists C(n – 1, k – 1) * F(k) different connected component C. Any graphs G(n-k) for remaining nodes are okay. So the answer is: 111( )( )( ) ()1nknF nG nF k G nkk It takes O(n^2) to calculate this formula. ...