选择若干条线段使权值最大，并且点覆盖次数不超过k。
建图如下：vs到0建立容量为k费用为0的边；坐标终点到vt连接一条容量为k费用为0的边；对于每两个相邻坐标连接一条容量为INF费用为0的边；对于线段每两个端点连接一条容量1费用为-cost的边。建图如下：vs到0建立容量为k费用为0
阅读背景：
POJ3680 Intervals（最小费用最大流）
来源：互联网
分享到：
