自闭场，题都没读几道 B. Black and white题意：给定一个n*m的棋盘，起初全白，将一个格子染黑需要代价$a[i][j]$，若某个矩形的四个角里有三个已经是黑色，则将第四个角染黑不需要任何代价，问将整个棋盘染黑的最小代价 转化为一个联通性问题，点1~n代表1~n行，点n+1~n+m代表1~m列，i和j+n之间连一条边权为$a[i][j]$用的边。$(i,j+n)$联通代表$(i,j)$​这个格子已被染黑，于是将整个棋盘染黑等价于整张图联通，即求该图的最小生成树 为啥问题等价呢，考虑$(i,j)$联通的两种可能性： $(i,j+n)$​​连了一条边，说明直接染黑 $(i_1,j_2)$​通过一些中间边如$(i_1,j_1),(i_2,j_1),(i_2,j_2)$​联通，意味着$(i_1,j_1),(i_2,j_1),(i_2,j_2)$已被染黑，显然这四个点构成矩形的四个角，$(i_1,j_2)$可以不花费代价染黑     阅读全文