POJ-3680：Intervals （费用流）

You are given N weighted open intervals. The ith interval covers (a_i, b_i) and weighs w_i. Your task is to pick some of the intervals to maximize the total weights under the limit that no point in the real axis is covered more than k times.

Input

The first line of input is the number of test case.
The first line of each test case contains two integers, N and K (1 ≤ K ≤ N ≤ 200).
The next N line each contain three integers a_i, b_i, w_i(1 ≤ a_i < b_i ≤ 100,000, 1 ≤ w_i ≤ 100,000) describing the intervals.
There is a blank line before each test case.

Output

For each test case output the maximum total weights in a separate line.

Sample Input

4

3 1
1 2 2
2 3 4
3 4 8

3 1
1 3 2
2 3 4
3 4 8

3 1
1 100000 100000
1 2 3
100 200 300

3 2
1 100000 100000
1 150 301
100 200 300

Sample Output

题意：给定N个带权线段，现在选一些线段，其和最大，而且每个点不被超过K个点覆盖。

思路：离散化，费用流模板题，求最大费用最大流，最大输出-ans。横向i->i+1，加边(i,i+1,K,0)；对于线段，加边(u,v,1,-cost);

（N个线段满足u<v，所以不用考虑成环的问题。

#include<deque>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define ll long long
#define maxn 410
#define inf 1<<30
using namespace std;
int To[maxn*10],Laxt[maxn*10],Next[maxn*10],cap[maxn*10],cost[maxn*10],dis[maxn*10];
int N,S,T,cnt,tot,ans; //费用
bool inq[maxn],vis[maxn];
deque<int>q;
void init() { cnt=1; ans=0; memset(Laxt,0,sizeof(Laxt)); S=0; T=tot+1; }
void add(int u,int v,int c,int cc) { Next[++cnt]=Laxt[u];Laxt[u]=cnt;To[cnt]=v;cap[cnt]=c;cost[cnt]=cc; }
bool spfa()
{
    memset(inq,0,sizeof(inq));
    for(int i=0;i<=T;i++) dis[i]=inf;
    inq[T]=1; dis[T]=0; q.push_back(T);
    while(!q.empty())
    {    
        int u=q.front(); q.pop_front();
        inq[u]=0;
        for(int i=Laxt[u];i;i=Next[i])
        {
            int v=To[i];
            if(cap[i^1]&&dis[v]>dis[u]-cost[i])
            {
                dis[v]=dis[u]-cost[i];
                if(!inq[u]){
                    inq[v]=1;
                    if(q.empty()||dis[v]>dis[q.front()]) q.push_back(v);
                    else q.push_front(v);
                }
            }
        }
    }
    return dis[S]<inf;
}
int dfs(int u,int flow)
{
    vis[u]=1;
    if(u==T||flow==0) return flow;
    int tmp,delta=0;
    for(int i=Laxt[u];i;i=Next[i])
    {
        int v=To[i];
        if((!vis[v])&&cap[i]&&dis[v]==dis[u]-cost[i])
        {
            tmp=dfs(v,min(cap[i],flow-delta));
            delta+=tmp; cap[i]-=tmp; cap[i^1]+=tmp;
        }
    }
    return delta;
}
int main()
{
    int Case,N,K,i,j;
    scanf("%d",&Case);
    while(Case--){
        scanf("%d%d",&N,&K);
        int u[210],v[210],w[210],b[420]; tot=0;
        for(i=1;i<=N;i++) {
            scanf("%d%d%d",&u[i],&v[i],&w[i]);
            b[++tot]=u[i]; b[++tot]=v[i];
        }
        sort(b+1,b+tot+1);
        tot=unique(b+1,b+tot+1)-(b+1);
        init();
        for(i=1;i<=N;i++){
            u[i]=lower_bound(b+1,b+tot+1,u[i])-b;
            v[i]=lower_bound(b+1,b+tot+1,v[i])-b;
            add(u[i],v[i],1,-w[i]); add(v[i],u[i],0,w[i]);
        }
        add(S,1,K,0);  add(1,S,0,0);
        add(T-1,T,K,0); add(T,T-1,0,0);
        for(i=1;i<T;i++) add(i,i+1,K,0),add(i+1,i,0,0);
        while(spfa())
        {
           vis[T]=1;
           while(vis[T])
           {
               memset(vis,0,sizeof(vis));
               int tmp=dfs(S,inf);
               ans+=(ll)tmp*dis[S];
           }
        }
        printf("%d
",-ans);
    }
    return 0;
}