|
|
| Line 8: |
Line 8: |
| | === Part B === | | === Part B === |
| | The easiest is just to run a preprocessing pass before running Kruskal's algorithm. Add all edges with negative weight, and all nodes connected to those edges. Then run Kruskal's algorithm normally until it is finished. | | The easiest is just to run a preprocessing pass before running Kruskal's algorithm. Add all edges with negative weight, and all nodes connected to those edges. Then run Kruskal's algorithm normally until it is finished. |
| − |
| |
| − | ----
| |
| − | === Part B alternative solution ===
| |
| − | <pre>
| |
| − | DFS on a graph to determine whether it contains edges with a negative weight, maintaining pointer MIN_E to one edge with the lowest non-negative weight
| |
| − | I. If there are no edges with a negative weight, then return MIN_E
| |
| − | - If all edges have a non-negative weight, then the minimum weight subset is the subset of 1 edge with the lowest weight
| |
| − | - A subgraph of 1 edge is connected
| |
| − |
| |
| − | II. If there are edges with a negative weight, then apply the Kruskal's algorithm
| |
| − | - Sort edges by their weight
| |
| − | - For each connectivity component, the total weight is stored in its representative, representative's weight updates in disjoint_set's union function, initial weight = 0
| |
| − | - Maintaining pointer MIN on the component with the lowest weight
| |
| − | - Loop over all edges
| |
| − | - - If edge's weight is negative, union components, if united component's weight is less than MIN, update MIN, continue
| |
| − | - - If edge's weight is positive and at least one of the components for union has a non-negative weight, continue
| |
| − | - - - Union with positive component via a positive edge can only increase weight, so the edge is skipped
| |
| − | - - If edge's weight is positive, weights of both components for union are negative, and (edges weight + weight of each component is negative), union components
| |
| − | - - - At this step, the algorithm does union 2 components with a negative weight via positive edge
| |
| − | - - - The weight of the combined component is less than the weight of each component separately, even though an edge with a positive weight was used
| |
| − | - - - If the weight of the combined component is less than MIN, update MIN
| |
| − | - return MIN
| |
| − | </pre>
| |
| − | --[[User:Bkarpov96|Bkarpov96]] ([[User talk:Bkarpov96|talk]]) 14:47, 22 July 2020 (UTC)
| |
Revision as of 22:52, 22 July 2020
Hints
Look very carefully at the definition of T, versus the definition of an MST.
Part A
The problem explicitly states that T is a "minimum weight connected subset", not "minimum weight connected subset with exactly N-1 edges", so it doesn't have to be an MST. If all weights are positive or zero, then T happens to be the same as the MST, but if negative weights are allowed, all negative weight edges must be included in T to drive the total as low as possible.
Part B
The easiest is just to run a preprocessing pass before running Kruskal's algorithm. Add all edges with negative weight, and all nodes connected to those edges. Then run Kruskal's algorithm normally until it is finished.
