电脑桌面
添加小米粒文库到电脑桌面
安装后可以在桌面快捷访问

男人八题解题报告

男人八题解题报告_第1页
1/15
男人八题解题报告_第2页
2/15
男人八题解题报告_第3页
3/15
[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. ...

1、当您付费下载文档后,您只拥有了使用权限,并不意味着购买了版权,文档只能用于自身使用,不得用于其他商业用途(如 [转卖]进行直接盈利或[编辑后售卖]进行间接盈利)。
2、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。
3、如文档内容存在违规,或者侵犯商业秘密、侵犯著作权等,请点击“违规举报”。

碎片内容

男人八题解题报告

确认删除?
VIP
微信客服
  • 扫码咨询
会员Q群
  • 会员专属群点击这里加入QQ群
客服邮箱
回到顶部