Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 29613 Accepted: 11750


Farmer John has been elected mayor of his town! One of his campaign promises was to bring internet connectivity to all farms in the area. He needs your help, of course. 
Farmer John ordered a high speed connection for his farm and is going to share his connectivity with the other farmers. To minimize cost, he wants to lay the minimum amount of optical fiber to connect his farm to all the other farms. 
Given a list of how much fiber it takes to connect each pair of farms, you must find the minimum amount of fiber needed to connect them all together. Each farm must connect to some other farm such that a packet can flow from any one farm to any other farm. 
The distance between any two farms will not exceed 100,000. 



Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 12785    Accepted Submission(s): 5135

Problem Description

1967年,美国著名的社会学家斯坦利·米尔格兰姆提出了一个名为“小世界现象(small world phenomenon)”的著名假说,大意是说,任何2个素不相识的人中间最多只隔着6个人,即只用6个人就可以将他们联系在一起,因此他的理论也被称为“六度分离”理论(six degrees of separation)。虽然米尔格兰姆的理论屡屡应验,一直也有很多社会学家对其兴趣浓厚,但是在30多年的时间里,它从来就没有得到过严谨的证明,只是一种带有传奇色彩的假说而已。 继续阅读六度分离

【并查集】ZOJ Problem Set – 3321 Circle


Time Limit: 1 Second      Memory Limit: 32768 KB

Your task is so easy. I will give you an undirected graph, and you just need to tell me whether the graph is just a circle. A cycle is three or more nodes V1V2V3, … Vk, such that there are edges between V1 and V2V2 and V3, … Vk and V1, with no other extra edges. The graph will not contain self-loop. Furthermore, there is at most one edge between two nodes.

继续阅读【并查集】ZOJ Problem Set – 3321 Circle

HDU P1232 畅通工程(并查集)

Problem Description
某省调查城镇交通状况,得到现有城镇道路统计表,表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通(但不一定有直接的道路相连,只要互相间接通过道路可达即可)。问最少还需要建设多少条道路? 继续阅读HDU P1232 畅通工程(并查集)