51Nod 1499 图
emmmmmmm不错的的最小割吧 唯一一个不是很好的点就是实在是太容易想到是最小割了,但是没想到具体的建图方法。 题意: 有n个点,m条边,要你分成两个集合,使得两个集合的导出子图各自权值和的和最大。 两个导出子图中,可选择其中一个,若导出子图中存在有两个点 (i,j) 相连,则该导出子图权值增加 $| i-j |$ 。同时另一个导出子图则相反,只有存在两个点没有边相连,才会增加权值。 思路: 题目的主要目的就是将点集分成两部分,这很容易想到二分图染色,但这是不现实的,因为这是一个最值问题,不存在必然关系。…