Cluster analysis辅导、辅导Python，c/c++，Java程序语言、讲解microorganisms 解析C/C++编程|讲解数据

Introduction
Cluster analysis or clustering is the task of grouping a set of objects in such a
way that objects in the same group (called a cluster) are more similar (in some
sense) to each other than to those in other groups (clusters). Clustering arises
whenever one has a collection of objects - say, a set of photographs,
documents, or microorganisms - that one is trying to classify or organize into
coherent groups.
The fundamental problem of clustering is very simple. That is, to divide into
clusters so that points in different clusters are far apart. Clustering is thus
widely used in many tasks, including data mining, routing, identifying patterns
in gene expression, document categorization, similarity searching in medical
image databases and Skycat.
Description
A long time ago in a galaxy far, far away, the country Mafghanistan
had n cities and m old roads, where each road connected a pair of cities. Due
to the treacherous mountains, there was no road or even path between some
cities (i.e., some cities were unreachable from others). During Operation
Mafghanistan Freedom, which spread democracy across Mafghanistan like
wildfire in Santa Barbara in the summer, the Mamerican forces evaporated all
the old roads in Mafghanistan. As the Commanding General of the Mamerican forces, you are in charge of Operation Mafghan Reconstruction, which will
build new roads in Mafghanistan subject to the following constraints:
Due to the treacherous mountains, you may build new roads only between the cities
where old roads existed before Operation Mafghanistan Freedom.
You should build enough new roads. However, since time is so limited, you should
stop after there have been k (, which means the threshold region number) regions in
Mafghanistan.
You should minimize the total lengths of the new roads to be built.
Define a region to be a set of cities that will be reachable from one another via
some new roads. Find all the regions using algorithms with good asymptotic
running times.
You may NOT use STL classes except the string class.
Input
Read input from cin. The input contains the number of cities (n), the number
of old roads (m), the threshold region number (k) and a series of old roads
where each road is represented by its two terminal cities and its length. Each
city is represented by a unique integer from 0 to n-1. Each road length is
represented by an integer. The following EBNFspecifies the input. Your
program need not handle invalid input (such as invalid file format or invalid
numbers representing cities). Although in general a graph may have multiple
minimum spanning trees, all the test cases are graphs with unique minimum
spanning trees.
n,m,k are less than 100,000. ::=

::= * * '\n'

::= * * *
* '\n'
::=
::=
::= +
::= '0'|'1'|'2'|'3'|'4'|'5'|'6'|'7'|'8'|'9'
::= ' ' | '\t'
Copy
Output
On the first line, print[
Print each region in the descending order of the number of cities in the region.For
each region:
o On the first line, print:[
o Then, print each new road per line in the descending order of the lengths of the
roads. For each new road, print its two terminal cities represented by their
numbers (print the smaller number before the larger number), and then the
length of the road, as in the following example:[0,10,20]Unless a road is the
last one in the region, print , immediately after the ] in the above line.
o On the last line, print:]Unless a region is the last one in the country,
print , immediately after the ] in the above line.
On the last line, print:]
Your program must exit with the exit code 0, i.e., call return 0 from the
function main() or call exit(0).Breaking ties
To break the tie when two roads e1=(s1, t1) and e2=(s2, t2) have the
same length, consider e1 to be shorter than e2if and only if
min(s1, t1) < min(s2, t2), or
min(s1, t1) == min(s2, t2) and max(s1, t1) < max(s2, t2)
To break the tie when two regions r1={...} and r2={...} have the same
number of cities, consider r1 to have fewer cities than r2 if and only
if min(r1) < min(r2), where min(s) returns the smallest member of the
set s. Note that regions are disjoint sets of cities.Sample
Input:
10
13
3
7 8 3
7 9 2
8 9 1
7 9 1
0 1 28
0 5 10
1 2 16
1 6 14
2 3 12
3 4 22
3 6 18
4 5 25
4 6 24
Copy
Output:
[
[
[3,4,22],
[1,2,16],
[1,6,14],
[2,3,12]
],
[
[8,9,1],
[7,9,1]
],
[
[0,5,10]
]
]
CopyHints
You probably need to implement disjoint sets, min heap, minimum spanning
trees, and an O(n log n) sorting algorithm (e.g., Heap Sort).
Algorithms to get clustering of a graph is very similar to that of minimum
spanning trees, with some minimal modifications.