Ex - Trespassing Takahashi Editorial by TangJing
Consider the proof of prim algorithm：
Lemma: for point \(i\), the edge with the smallest edge weight with point \(i\) as the endpoint must be the edge in the minimum spanning tree.
Lemma proof
Assuming that the edge satisfying the lemma condition is $(i,u)$, take any minimum spanning tree $G$ without edge $(i,u)$ and add edge $(i,u)$ to $G$. at this time, it will form a ring, and the existence of edge $(i,v)$ satisfies that both $(i,u)$ and $(i,v)$ are edges in the ring. Because $(i,u)$ is the edge with the smallest edge weight with $i$ as the endpoint, it must satisfy $w (i, v)\ge w (i, u)$. If $w (i, v)>w(i,u)$, it is in contradiction with $G$ being the minimum spanning tree, Because removing $(i,v)$ from the ring will get the minimum spanning tree with smaller weight than $G$, so $w (i, v)=w (i, u)$. Removing $(i, v)$ will get $(i, u)$ in the minimum spanning tree.Prove prim algorithm
For a point $s$, find the edge with the smallest edge weight with point $s$ as the endpoint, suppose this edge is $(s, u)$.Add the edge $(s,u)$ to the edge set of the minimum spanning tree, and merge point $u$ into point $s$, and merge the corresponding edge set at the same time.Assuming that there are originally $n$ points, after this operation, it is transformed into a subproblem with problem scale of $n-1$. Through induction, we can get that prim obtains a minimum spanning tree.Modified prim algorithm based on lemma:
Numeration \(i=1,2,...,n:\)
Find the edge \((i,u)\) with the smallest edge weight with \(i\) as the endpoint. If adding edge \((i,u)\) will not form a ring, add edge\((i,u)\) into minimum spanning tree.
The algorithm will add at least \(\lfloor\frac{n}{2}\rfloor\) edges.
By shrinking the points and applying the above algorithm repeatedly, the minimum spanning tree problem can be solved in \(O (mlogn)\) time.
Then the key to solving the problem abc250h is that for the key point \(i=1,2,...,K\). Find the key point with the shortest distance from key point \(i\).The solution to this problem can be referred to abc245g.
The total time complexity is \(o (mlogklogn)\).
posted:
last update: