标签: 曼哈顿最小生成树

「HDU 6506」Spin A Web

We have a canvas divided into grid with H rows and W columns. The square at the ith row from the top and the jth column from the left is represented as (i, j). (i, j) square has two value xi,j and yi,j .
Now we want to merge the squares to a connected web with minimal cost. Two squares can be connected if they are in the same row or column, and the cost of connecting (i0, j0) and (i1, j1) is|x_i0,j0 - xi1,j1| + |yi0,j0 - yi1,j1|