G - Intervals（最小费用流，指派问题）

G - Intervals

题意：

求n个区间，从中选取一些区间，使得每个点最多被覆盖k次，使得权值和最大。

分析：

等效问题：选出一些区间，使得区间分成 $k$ 个区间集合。每个集合里面区间不相交，要求总权值和最大。

网络流将所有端点排序，相邻节点连接一条费用为 $0$ ，容量为 $i n f$ 的边，对于每个区间 $i$ ， $a$ 到 $b$ 端点连接一条费用为 $- w [i]$ 的边。容量为 $1$ 。那么求最小费用流，每一个流都代表一个不重叠的区间选取。其权值和等于费用的相反数。

#include<queue>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#define mset(a,b) memset(a,b,sizeof(a))
using namespace std;
const int maxn=500;//顶点数量
const int inf=0x3f3f3f3f;
/*求n个区间，从中选取一些区间，使得每个点最多被覆盖k次 等效问题：选出一些区间，使得区间分成k个集合。每个集合区间不相交，要求容量最大 网络流将所有端点排序，相邻节点连接一条费用为0，容量为inf的边，对于每个区间i，a到b端点连接一条费用为-w[i]的边。容量为1 那么求最小费用流，每一个流都代表一个不重叠的区间选取。其权值等于费用的相反数 */
struct edge
{
    int to,cap,cost,rev;
    edge() {}
    edge(int to,int cap,int cost,int rev)
    {
        this->to=to,this->cap=cap,this->cost=cost,this->rev=rev;
    }
};
class MCMF
{
public:
    vector<edge> adja[maxn];
    int dis[maxn],prevv[maxn],preve[maxn],top;
    bool inque[maxn];
    void init(int n)
    {
        for(int i=0; i<n; ++i)    adja[i].clear();
        top=n;
    }
    void addEdge(int u,int v,int f,int cost)
    {
        adja[u].push_back(edge(v,f,cost,adja[v].size()));
        adja[v].push_back(edge(u,0,-1*cost,adja[u].size()-1));
    }
    bool spfa(int s,int t)
    {
        queue<int> mp;
        mset(dis,inf);mset(prevv,-1);mset(inque,0);
        mp.push(s),prevv[s]=s,dis[s]=0,inque[s]=true;
        while(!mp.empty())
        {
            int u=mp.front();
            mp.pop();
            inque[u]=false;
            for(int i=0; i<adja[u].size(); ++i)
            {
                edge& e=adja[u][i];
                if(e.cap>0&&dis[e.to]>dis[u]+e.cost)
                {
                    dis[e.to]=dis[u]+e.cost;
                    prevv[e.to]=u;
                    preve[e.to]=i;
                    if(!inque[e.to])
                    {
                        inque[e.to]=true;
                        mp.push(e.to);
                    }
                }
            }
        }
        if(~prevv[t]) return true;
        return false;
    }
//他的第三个函数也可以这样写，即满足流f的最小花费
    int minCostMaxFlow(int s,int t,int f) //不能满足流f则返回-1
    {
        int cost=0;
        while(f>0)
        {
            spfa(s,t);
            if(dis[t]==inf)
                return cost;
            int d=f;
            for(int v=t; v!=prevv[v]; v=prevv[v]) //找到d
                d=min(d,adja[prevv[v]][preve[v]].cap);
            cost+=d*dis[t];
            f-=d;
            for(int v=t; v!=prevv[v]; v=prevv[v])
            {
                edge &e=adja[prevv[v]][preve[v]];
                e.cap-=d;
                adja[v][e.rev].cap+=d;
            }
        }
        return cost;
    }

};
/* 建图： 1.所有端点排序，相邻节点连接一条费用为0，容量为inf的边， 2.对于每个区间i，a到b端点连接一条费用为-w[i]的边。容量为1 3.k的最小费用即可 */
MCMF kit;
vector<int> V;
struct Seg{
int a,b,w;
Seg(){}
Seg(int a,int b,int w):a(a),b(b),w(w){}
};
vector<Seg> seg;
int main()
{
    int n,k,t;
    scanf("%d",&t);
    while(t--){
        scanf("%d %d",&n,&k);
        V.clear(); seg.clear();
        for(int i=0;i<n;++i){
            int a,b,w;
            scanf("%d%d%d",&a,&b,&w);
            V.push_back(a);
            V.push_back(b);
            seg.push_back(Seg(a,b,w));
        }
        sort(V.begin(),V.end());
        V.erase(unique(V.begin(),V.end()),V.end());
        int s=0,t=V.size()-1,m=V.size();
        kit.init(m);
        for(int i=0;i<m-1;++i) kit.addEdge(i,i+1,inf,0);
        for(int i=0;i<n;++i) {
            int ath,bth;
            ath=lower_bound(V.begin(),V.end(),seg[i].a)-V.begin();
            bth=lower_bound(V.begin(),V.end(),seg[i].b)-V.begin();
            kit.addEdge(ath,bth,1,-1*seg[i].w);
        }
        int ans=kit.minCostMaxFlow(s,t,k)*-1;
        printf("%d\n",ans);
    }
    return 0;
}