POJ 3680 - Intervals
Problem : Some segment (ai, bi) [ai<bi] with weight wi. Choose some segments to make weight maximum and, at the same time, each segment does internally intersect with no more than k-1 other chosen segments. N, K<=200.
Solution : Discretization the endpoint first, then construct graph for maximum cost maximum flow. Vertex are source, sink, and endpoints. source->0 with (k, 0), n-1->sink with (k, 0), i->i+1 with (k, 0), ai->bi with (1, wi). Obviously it's DAG, thus maximum cost maximum flow is realizable.
Proof : To prove its correctness, the following lemma is enough.
Lemma - For the given segments set S, there is k sets of non-internal-intersect segments whose union is S if and only if there is no segment does internally intersect with more than k-1 other segments in S.
-> : Obviously. k non-internal-intersect segment sets has no interval used more than k times.
<- : The k non-internal-intersect segments sets can be constructed in following way: insert segment i in ascending order of ai, choose any one set as long as it has no element intersect with i. It's impossible that k sets are all invalid, if it does, since all previously inserted segments has start point <= ai, there must exist k segments with end point >ai, and use interval (ai, ai+1) already k times before inserting i, contradicting the fact that no segment intersect with more than k-1 segments (k+1 segments has interval (ai, ai+1)).