每个区间是一个节点。
· 从每个节点到汇点有一条边，容量为1，费用为该区间的权重的负数。
· 如果两个区间i和j不冲突，则从节点i向j连一条边，容量为1，费用为区间i的权重的负数。为了不使图中出现环，我把区间从左到右排序，只从左边的区间向右的区间连边。
· 从源点到每个区间的节点连一条边，容量为1，费用为0。
· 另加一个源点，向原来的源点边一条边，容量为K，费用为0。

然后求最小费用费大流，费用的负数就是答案。我这样做对吗？

• 有人能帮帮忙回答我一下吗？ (0) ImLazy 2008-09-29 12:29:22