Description
Assume you are a route planner for a logistics company, responsible for establishing pathways between cities to ensure efficient transportation of goods. Your job is to identify a minimal-cost connectivity route to ensure connectivity between all cities while minimizing the overall transportation cost. Let a graph represent the map of those cities, where each edge is the pathway between cities and the edge weight is the cost to travel between two cities. We define a minimal-cost connectivity route as the minimum cost spanning tree of the graph.
Without a doubt, you may discover multiple minimal-cost connectivity routes. Within these routes, if some pathways always appear in all minimal-cost connectivity routes, then we will consider them as “essential links”. Additionally, if some pathways only exist in certain minimal-cost connectivity routes, we will consider them as “secondary links”. Finding these links helps company to further optimize resource allocation.
Given an undirected graph where each node represents a city and an edge denotes a pathway between two cities, you need to develop an algorithm to find the minimum cost of all connectivity routes and calculate the number of essential and secondary links respectively.
For example:
There are 4 cities indexed from 0 to 3, and their connections are shown in the figure below.
The minimum cost would be 4, and the corresponding minimal-cost connectivity routes are:
From the route above, we can find that the pathway between cities 0, 1, and cities 2, 3 appear in all the routes. Therefore, they are essential links.
As for the connections between cities 0, 2 and cities 1, 3, they don’t appear in every route, so they are secondary links.
You can use std::vector, but other STL library are forbidden.
12/16 Update:
You can also use std::sort
There is at least one mst in each testcase.
Input
The first line contains an integer N, which is the number of cities, and the cities are indexed from 0 to N-1.
0 < N < 300
The second line contains an integer E, which is the number of connections.
1 <= E <= N(N-1) / 2
The following E lines indicate which two cities have pathway. Each line contains three integers A B W, which means that there is a pathway between cities A and B with a cost W
Output
You need to output the cost of the minimal-cost connectivity route in the first line. In the second and third lines, you need to output the number of essential links and number of secondary links, respectively.