Topcoder SRM 503 DIV1 500P 编程比赛题目分析及源码

LV2 500P 王国的城乡 KingdomXCitiesandVillages

题目大意：王国有多个城市和村庄，开始没有道路（连接两点的线段），假设建造道路的过程如下，先找出任意一个没有道路的村庄，将其与最近的点连接（这个点要是城市或直接间接连接到城市的村庄），如果距离相同就等概率任选一个。求总道路长度的期望。

分析：对于任何一个村庄只要求出它连接到系统的期望，最后求和即可。对到某个村庄A的距离进行排序，只需要处理小于最近城市的那些，因为如果距离长于城市，就不如直接连接城市了。排序后，对于任意的村庄B，要是被选择与A连接，说明比B离A近的那些村庄都还没有连接到系统。比如小于B的村庄有x个，那么所有情况就是(x+2)!，因为还有A和B要参与排序。小于B的x个要排在B后面，他们之间可以乱序，就是x!，所以概率就是x!/(x+2)!=1/(x+1)/(x+2)，用概率乘上距离求和即可。最后不要忘记还有最近的那个城市，将概率的剩余部分给城市就行了。多个村庄相等的情况不需要考虑，可以假设有微小的差别，排序处理，结果是一样的。-Topcoder SRM 503 DIV1 500P programming contest problem analysis and source code

LV2 500P kingdom urban KingdomXCitiesandVillages

Subject to the effect: Kingdom of cities and villages, no roads begin (line connecting the two points), assuming that the process of construction of roads as follows, first find no roads at any one village to the nearest point of connection (at this point if the city ​ ​ or directly or indirectly connected to the city s village), if the distance is the same as the probability of either one on the other. Find the total road length of expectations.

Analysis: calculated for any one village as long as it is connected to the system s expectations, final summation can be. A village on the distance to a sort, just less than the nearest city to deal with those, because if the distance is longer than the city, it should be directly connected city. After sorting, for any village B, if the connection is selected with the A, B from A descr iption than those n