Difference between revisions of "TADM2E 6.9"
From Algorithm Wiki
(create page) |
(Add hint) |
||
| 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. | 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. | ||
Revision as of 18:50, 23 April 2015
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.
