POJ 3680_Intervals

题意：

给定区间和该区间对应的权值，挑选一些区间，求使得每个数都不被K个区间覆盖的最大权值和。

分析：

如果K=1，即为区间图的最大权独立集问题。可以对区间所有端点排序后利用动态规划的方法，设dp[i]为只考虑区间右端点小于等于xi的区间所得到的最大总权重。

dp[i] = max(dp[i - 1], max{dp[j] + w[k])|a[k] = x[j]且b[k] = x[i]}

K>1，既然求权重最大值，利用最小费用流，很容易想到从a[i]到b[i]连一条容量为1，费用为−w[i]的边，但是如何限制每个数不被超过K个区间覆盖呢？从i到i+1连一条容量为K，费用为0的边，这样便限制了流经每个端点的流量不超过K，也就满足每个数不被超过K个区间覆盖啦~注意区间端点的离散化~~

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
using namespace std;
const int maxn = 505, maxm = 1000;
const int INF = 0x3f3f3f3f;
int s, t, tot;
int dist[maxm], prevv[maxm], preve[maxm], head[maxm];
int a[maxn], b[maxn], w[maxn], tt[maxm];
bool in[maxn];
struct Edge{ int from, to, next, cap, cost;}edge[maxm * 3];
void add_edge(int from, int to, int cap, int cost)
{
   edge[tot].to = to;
   edge[tot].from = from;
   edge[tot].cap = cap;
   edge[tot].cost = cost;
   edge[tot].next = head[from];
   head[from] = tot++;
   edge[tot].to = from;
   edge[tot].from = to;
   edge[tot].cap = 0;
   edge[tot].cost = -cost;
   edge[tot].next = head[to];
   head[to] = tot++;
}
int mincost()
{
    int flow=0, cost=0;
    for(;;){
        memset(dist, 0x3f, sizeof(dist));
        memset(in, false, sizeof(in));
        queue<int>q;
        q.push(s);
        in[s] = true;
        dist[s]=0;
        while(!q.empty()){
            int u = q.front();q.pop();
            in[u] = false;
            for(int i = head[u]; i != -1; i = edge[i].next){
                Edge e = edge[i];
                if(e.cap>0 && dist[e.to] > dist[u] + e.cost){
                    dist[e.to] = dist[u] + e.cost;
                    prevv[e.to] = u, preve[e.to] = i;
                    if(!in[e.to]){
                        in[e.to] = true;
                        q.push(e.to);
                    }
                }
            }
        }
        if(dist[t] == INF)  return cost;
        int d = INF;
        for(int i = t; i != s; i = prevv[i])
            d = min(d, edge[preve[i]].cap);
        flow += d;
        cost += dist[t] * d;
        for(int i = t; i != s; i = prevv[i]){
            edge[preve[i]].cap -= d;
            edge[preve[i]^1].cap += d;
        }
    }
}
int main()
{
    int c;scanf("%d",&c);
    while(c--){
        int N, K;
        memset(head,-1,sizeof(head));
        tot = 0;
        int n = 0;
        scanf("%d%d",&N, &K);
        for(int i = 0; i < N; i++){
            scanf("%d%d%d", &a[i], &b[i], &w[i]);
            tt[n++] = a[i];
            tt[n++] = b[i];
        }
        sort(tt, tt + n);
        int nn = unique(tt, tt +n) - tt;
        int na, nb;
        for(int i = 0; i < N; i++){
            na = lower_bound(tt, tt + nn, a[i]) - tt;
            nb = lower_bound(tt, tt + nn, b[i]) - tt;
            add_edge(na + 1, nb + 1, 1, -w[i]);
        }
        s = 0, t = nn + 1;
        add_edge(s, 1, K, 0);
        for(int i = 1; i <= nn; i++)
            add_edge(i, i + 1, K, 0);
        printf("%d
",-mincost());
    }
    return 0;
}

其实这题也可以是从i+1向i连一条容量为1，权值为w[i]的边，用求出的最小费用流减去所有区间权值和，再取负数就好啦~实际上是取最小费用流对应的区间之外的区间，因为建图保证每个点都不被超过K个区间覆盖，所以不用担心与题目不符啦~~

tle了一整天。。。。
很巧妙的构图~~~