不难观察到一个性质：可以找到一条边\((i,i+1)\)，满足存在一个最优解，其所有匹配的路径不经过这条边，称之为分界线。可以调整证明。如果我们已知了分界线，不妨设为\((m,1)\)。那么最小权匹配就是类似括号匹配，贪心扫一遍即可。这个不是很好优化，考虑对每条边算贡献。不妨令两类点的权