Cluster analysis代写、代写Python，c/c++，Java程序语言、代做microorganisms

日期：2019-02-12 11:36

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.

<input> ::= <num-cities> <num-old-roads> <threshold-regionnumber>

<old-road>*

<num-cities> ::= <ws>* <number> <ws>* '\n'

<num-old-roads> ::= <ws>* <number> <ws>* '\n'

<threshold-region-number> ::= <ws>* <number> <ws>* '\n'

<old-road> ::= <ws>* <city> <ws> <ws>* <city> <ws> <ws>*

<length> <ws>* '\n'

<city> ::= <number>

<length> ::= <number>

<number> ::= <digit>+

<digit> ::= '0'|'1'|'2'|'3'|'4'|'5'|'6'|'7'|'8'|'9'

<ws> ::= ' ' | '\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]

]

]

Copy

Hints

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.