Minimum spanning tree subproblem:POJ 1287
The priM algorithm of minimum spanning tree has not been learned, and it seems that the most short circuit will also use this idea, so today I learned, looked for a lot of blogs, algorithm diagrams are quite good, but the code implementation is very complex, and finally found a template problem solving blog to read the code implementation.
Prim is a very simple algorithmKeep looking for the current distance
The generated treeThe smallest node is added to the tree, until all the nodes are in the tree.
Ps: If the algorithm is not clear, take a look at this blog's illustration: Portal.
Know the train of thought, next look at the above template problem, and then carefully, patient simulation of the following code should be no problem.
Today's efficiency is low, only look at such an algorithm... (So impetuous!!)