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

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

• 这是我的建图 但是我TLE了 (654) 20053565 2008-09-29 12:51:52
  • 我基本明白你的意思了。这样就是有最多400个节点，600条边，应该说规模不算大啊。不过我觉得case数可能很多，因为我cin就TLE，scanf就WA。等我也试试看你的图再说。 (0) ImLazy 2008-09-29 15:36:52
  • 我用你的构图法AC了。谢谢。 (0) ImLazy 2008-09-29 21:24:41
    • 啊，看来我的费用流写的太垃圾了，能发我下你的code么？ (0) 20053565 2008-09-29 21:38:10
      • 好的，我已经发好了。 (0) ImLazy 2008-09-30 19:41:54
  • 用邻接表吧～ Yen's improvement 加速 (722) cuiaoxiang 2008-09-30 23:38:35
  • Re:这是我的建图 但是我TLE了 (742) abilitytao 2010-03-30 16:11:30