Difference between revisions of "TADM2E 6.9"
From Algorithm Wiki
(create page) |
(Undo revision 878 | Why are u doing this? What's the point? It's wiki for learning book) |
||
| (3 intermediate revisions by 3 users not shown) | |||
| Line 1: | Line 1: | ||
| + | === Hints === | ||
| + | Look very carefully at the definition of T, versus the definition of an MST. | ||
| + | |||
| + | |||
=== Part A === | === 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. | 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 === | === 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. | ||
| − | + | ---- | |
| + | === 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) | ||
Latest revision as of 08:13, 23 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.
Part B alternative solution
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
