题意:
给你n个任务,k个机器,n个任务的起始时间,持续时间,完成任务的获利
每个机器可以完成任何一项任务,但是同一时刻只能完成一项任务,一旦某台机器在完成某项任务时,直到任务结束,这台机器都不能去做其他任务
最后问你当获利最大时,应该安排那些机器工作,即输出方案
分析:
要求的是最大费用,因此将费用取负就可以用最小费用最大流算法了
建图很重要。如果图建的复杂的话,可能就会超时了的!
新建源汇S T‘
对任务按照起始时间s按升序排序
拆点:
u 向 u'连一条边 容量为 1 费用为 -c,
u' 向 T连一条边 容量为 inf 费用为 0;
如果任务u完成后接下来最先开始的是任务v
则从u' 向 v连一条边,容量inf 费用 0.
另外,任务从前往后具有传递性,所以必须是第i个任务向第i+1个任务建边,容量为inf
// File Name: 164-C.cpp
// Author: Zlbing
// Created Time: 2013年08月13日 星期二 14时57分55秒 #include<iostream>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<cstdio>
#include<set>
#include<map>
#include<vector>
#include<cstring>
#include<stack>
#include<cmath>
#include<queue>
using namespace std;
#define CL(x,v); memset(x,v,sizeof(x));
#define INF 0x3f3f3f3f
#define LL long long
#define REP(i,r,n) for(int i=r;i<=n;i++)
#define RREP(i,n,r) for(int i=n;i>=r;i--)
const int MAXN=2e3+;
struct Edge{
int from,to,cap,flow,cost;
};
struct MCMF{
int n,m,s,t;
vector<Edge>edges;
vector<int> G[MAXN];
int inq[MAXN];
int d[MAXN];
int p[MAXN];
int a[MAXN];
void init(int n){
this->n=n;
for(int i=;i<=n;i++)G[i].clear();
edges.clear();
}
void AddEdge(int from,int to,int cap,int cost){
edges.push_back((Edge){from,to,cap,,cost});
edges.push_back((Edge){to,from,,,-cost});
m=edges.size();
G[from].push_back(m-);
G[to].push_back(m-);
}
bool BellmanFord(int s,int t,int& flow,int& cost){
for(int i=;i<=n;i++)d[i]=INF;
CL(inq,);
d[s]=;inq[s]=;p[s]=;a[s]=INF; queue<int>Q;
Q.push(s);
while(!Q.empty()){
int u=Q.front();Q.pop();
inq[u]=;
for(int i=;i<(int)G[u].size();i++){
Edge& e=edges[G[u][i]];
if(e.cap>e.flow&&d[e.to]>d[u]+e.cost){
d[e.to]=d[u]+e.cost;
p[e.to]=G[u][i];
a[e.to]=min(a[u],e.cap-e.flow);
if(!inq[e.to]){
Q.push(e.to);
inq[e.to]=;
}
}
}
}
if(d[t]==INF)return false;
flow+=a[t];
cost+=d[t]*a[t];
int u=t;
while(u!=s){
edges[p[u]].flow+=a[t];
edges[p[u]^].flow-=a[t];
u=edges[p[u]].from;
}
return true;
}
int Mincost(int s,int t){
int flow=,cost=;
while(BellmanFord(s,t,flow,cost));
return cost;
}
};
struct node{
int u, v,cost,id ;
bool operator <(const node &rsh)const
{
return u<rsh.u;
}
}pos[MAXN];
MCMF solver;
int ans[MAXN];
int main()
{
int n,m;
while(~scanf("%d%d",&n,&m))
{
int a,b,c;
solver.init(*n+);
REP(i,,n-)
{
scanf("%d%d%d",&a,&b,&c);
pos[i]=(node){
a,a+b-,c,i
};
}
sort(pos,pos+n);
int s=n*,t=n*+;
REP(i,,n-)
{
solver.AddEdge(i,i+n,,-pos[i].cost);
solver.AddEdge(i+n,t,INF,);
if(i<n-)solver.AddEdge(i,i+,INF,);
for(int j=i+;j<n;j++)
{
if(pos[i].v<pos[j].u)
{
solver.AddEdge(i+n,j,INF,);
break;
}
}
}
solver.AddEdge(s,,m,);
solver.AddEdge(n-,t,m,);
solver.Mincost(s,t);
//printf("cost=%d\n",-tmp);
CL(ans,);
for(int i=;i<(int)solver.edges.size();i++)
{
Edge e=solver.edges[i];
if(e.cap)
{
int u=e.from;
if(u!=s&&u!=t&&u<n&&e.flow==e.cap)
{
ans[pos[u].id]=;
}
}
}
for(int i=;i<n;i++)
{
if(i)printf(" ");
printf("%d",ans[i]);
}
printf("\n");
}
return ;
}