Machine Programming

One remarkable day company “X” received k machines. And they were not simple machines, they were mechanical programmers! This was the last unsuccessful step before switching to android programmers, but that’s another story.

The company has now n tasks, for each of them we know the start time of its execution si, the duration of its execution ti, and the company profit from its completion ci. Any machine can perform any task, exactly one at a time. If a machine has started to perform the task, it is busy at all moments of time from si to si + ti - 1, inclusive, and it cannot switch to another task.

You are required to select a set of tasks which can be done with these k machines, and which will bring the maximum total profit.

Input
The first line contains two integer numbers n and k (1 ≤ n ≤ 1000, 1 ≤ k ≤ 50) — the numbers of tasks and machines, correspondingly.

The next n lines contain space-separated groups of three integers si, ti, ci (1 ≤ si, ti ≤ 109, 1 ≤ ci ≤ 106), si is the time where they start executing the i-th task, ti is the duration of the i-th task and ci is the profit of its execution.

Output
Print n integers x1, x2, …, xn. Number xi should equal 1, if task i should be completed and otherwise it should equal 0.

If there are several optimal solutions, print any of them.

Examples
inputCopy
3 1
2 7 5
1 3 3
4 1 3
outputCopy
0 1 1
inputCopy
5 2
1 5 4
1 4 5
1 3 2
4 1 2
5 6 1
outputCopy
1 1 0 0 1
Note
In the first sample the tasks need to be executed at moments of time 2 … 8, 1 … 3 and 4 … 4, correspondingly. The first task overlaps with the second and the third ones, so we can execute either task one (profit 5) or tasks two and three (profit 6).

一道比较正常的费用流。没有那么裸。

如果对费用流稍微有一些了解，那么暴力建图不难想到。但是这样建图的边数是O(n)的，不管是Dijkstra势函数，还是zkw都会TLE。

那么我们想一下刚刚的暴力建图：
很多边都是浪费的，比如一个很前面的点，连向了很后面的点，大概率这两个点之间都会间隔其他的点。
所以我们先对每个任务按照开始时间排序。
对于当前任务，如果不执行，那么连向下一个任务。如果执行则连向下一个可以执行的任务。

怎么实现，任务的执行或者不执行呢？直接对任务拆点，分为入点和出点，若到达出点则为执行。

这样的连边就是O(n)的数量，完全OK。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int inf=0x3f3f3f3f;
const int N=2e3+10,M=1e6+10;
int n,k,s,ps,t,d[N],st[N],vis[N],res[N],cost;
int head[N],nex[M],to[M],w[M],flow[M],tot=1;
struct node{int bg,ed,c,id;}q[N];
int cmp(node a,node b){return a.bg<b.bg;}
inline void ade(int a,int b,int c,int d){
	to[++tot]=b; nex[tot]=head[a]; w[tot]=d; flow[tot]=c; head[a]=tot;
}
inline void add(int a,int b,int c,int d){ade(a,b,c,d);	ade(b,a,0,-d);}
inline int spfa(){
	memset(st,0,sizeof st);	queue<int> q;	q.push(s);
	memset(d,-inf,sizeof d); d[s]=0; vis[s]=1;
	while(q.size()){
		int u=q.front();	q.pop();	vis[u]=0;
		for(int i=head[u];i;i=nex[i]){
			if(flow[i]&&d[to[i]]<d[u]+w[i]){
				d[to[i]]=d[u]+w[i];
				if(!vis[to[i]])	vis[to[i]]=1,q.push(to[i]);
			}
		}
	}
	return d[t]>=0;
}
int dfs(int x,int f){
	if(x==t)	return cost+=d[t]*f,f;
	st[x]=1;	int fl=0;
	for(int i=head[x];i&&f;i=nex[i]){
		if(flow[i]&&!st[to[i]]&&d[to[i]]==d[x]+w[i]){
			int mi=dfs(to[i],min(flow[i],f));
			flow[i]-=mi,flow[i^1]+=mi,fl+=mi,f-=mi;
		}
	}
	return fl;
}
signed main(){
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	cin>>n>>k;	t=n*2+1;	add(s,1,k,0);
	for(int i=1;i<=n;i++)	cin>>q[i].bg>>q[i].ed>>q[i].c,q[i].id=i;
	sort(q+1,q+1+n,cmp);
	for(int i=1;i<=n;i++){
		add(i,i+n,1,q[i].c); add(i+n,t,inf,0); 
		if(i!=n)	add(i,i+1,inf,0);	
		for(int j=i+1;j<=n;j++){
			if(q[j].bg>q[i].bg+q[i].ed-1){
				add(i+n,j,inf,0);	break;
			}
		}
	}
	while(spfa())	dfs(s,inf);
	for(int i=1;i<=n;i++){
		for(int j=head[i];j;j=nex[j])
			if(to[j]==i+n&&flow[j^1]&&w[j])	res[q[i].id]=1;
	}
	for(int i=1;i<=n;i++)	cout<<res[i]<<' ';puts("");
	return 0;
}