口胡

这个网格图求最小割即求对偶图上最短路。对于任意两个附加点之间的空间都是一个点（同色边权为 0），然后两两配对，如果存在路径有交集的，一定不是最优的（这里在思考时花的时间多，我也不知道为啥……），那么 $\mathcal{O}\left(\left(\sum k\right)nm\log nm\right)$ 建二分图，其中对数是跑最短路的时间。对这个二分图跑最优匹配即可。