The Bonus Salary!
This problem will be judged on PKU. Original ID: 3762
64-bit integer IO format: %lld Java class name: Main
In order to encourage employees' productivity, ACM Company has made a new policy. At the beginning of a period, they give a list of tasks to each employee. In this list, each task is assigned a "productivity score". After the first K days, the employee who gets the highest score will be awarded bonus salary.
Due to the difficulty of tasks, for task i-th:
- It must be done from hh_Li : mm_Li : ss_Li to hh_Ri : mm_Ri : ss_Ri.
- This range of time is estimated very strictly so that anyone must use all of this time to finish the task.
Moreover, at a moment, each employee can only do at most one task. And as soon as he finishes a task, he can start doing another one immediately.
XYY is very hard-working. Unfortunately, he's never got the award. Thus, he asks you for some optimal strategy. That means, with a given list of tasks, which tasks he should do in the first K days to maximize the total productivity score. Notice that one task can be done at most once.
Input
The first line contains 2 integers N and K (1 ≤ N ≤ 2000, 0 ≤ K ≤ 100), indicating the number of tasks and days respectively. This is followed by N lines; each line has the following format:
hh_Li:mm_Li:ss_Li hh_Ri:mm_Ri:ss_Ri w
Which means, the i-th task must be done from hh_Li : mm_Li : ss_Li to hh_Ri : mm_Ri : ss_Ri and its productivity score is w. (0 ≤hh_Li, hh_Ri ≤ 23, 0 ≤mm_Li, mm_Ri, ss_Li, ss_Ri≤ 59, 1 ≤ w ≤ 10000). We use exactly 2 digits (possibly with a leading zero) to represent hh, mm and ss. It is guaranteed that the moment hh_Ri : mm_Ri : ss_Ri is strictly later thanhh_Li : mm_Li : ss_Li.
Output
The output only contains a nonnegative integer --- the maximum total productivity score.
Sample Input
5 2
09:00:00 09:30:00 2
09:40:00 10:00:00 3
09:29:00 09:59:00 10
09:30:00 23:59:59 4
07:00:00 09:31:00 3
Sample Output
16
Hint
The optimal strategy is:
Day1: Task1, Task 4
Day2: Task 3
The total productivity score is 2 + 4 + 10 = 16.
解题：最小费用最大流。离散化时间点。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <climits>
#include <vector>
#include <queue>
#include <cstdlib>
#include <string>
#include <set>
#include <stack>
#define LL long long
#define pii pair<int,int>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = ;
struct arc{
int v,w,f,next;
arc(int x = ,int y = ,int z = ,int nxt = ){
v = x;
w = y;
f = z;
next = nxt;
}
};
arc e[];
int head[maxn],d[maxn],p[maxn],tot,S,T;
bool in[maxn];
int n,m,lisan[maxn<<],cnt,x[maxn],y[maxn],sc[maxn];
void add(int u,int v,int w,int f){
e[tot] = arc(v,w,f,head[u]);
head[u] = tot++;
e[tot] = arc(u,-w,,head[v]);
head[v] = tot++;
}
queue<int>q;
bool spfa(){
for(int i = S; i <= T; i++){
d[i] = INF;
p[i] = -;
in[i] = false;
}
while(!q.empty()) q.pop();
d[S] = ;
in[S] = true;
q.push(S);
while(!q.empty()){
int u = q.front();
q.pop();
in[u] = false;
for(int i = head[u]; ~i; i = e[i].next){
if(e[i].f > && d[e[i].v] > d[u] + e[i].w){
d[e[i].v] = d[u] + e[i].w;
p[e[i].v] = i;
if(!in[e[i].v]){
in[e[i].v] = true;
q.push(e[i].v);
}
}
}
}
return p[T] > -;
}
int solve(){
int tmp = ,minV;
while(spfa()){
minV = INF;
for(int i = p[T]; ~i; i = p[e[i^].v])
minV = min(minV,e[i].f);
for(int i = p[T]; ~i; i = p[e[i^].v]){
tmp += minV*e[i].w;
e[i].f -= minV;
e[i^].f += minV;
}
}
return tmp;
}
int main(){
int hh,mm,ss;
while(~scanf("%d %d",&n,&m)){
tot = cnt = ;
memset(head,-,sizeof(head));
for(int i = ; i < n; i++){
scanf("%d:%d:%d",&hh,&mm,&ss);
x[i] = hh* + mm* + ss;
lisan[cnt++] = x[i];
scanf("%d:%d:%d",&hh,&mm,&ss);
y[i] = hh* + mm* + ss;
lisan[cnt++] = y[i];
scanf("%d",sc+i);
}
sort(lisan,lisan+cnt);
int cnt1 = ;
for(int i = ; i < cnt; i++)
if(lisan[i] != lisan[cnt1-]) lisan[cnt1++] = lisan[i];
cnt = cnt1;
S = ;
T = cnt;
for(int i = ; i < cnt; i++) add(i,i+,,m);
for(int i = ; i < n; i++){
int tx = lower_bound(lisan,lisan+cnt,x[i]) - lisan;
int ty = lower_bound(lisan,lisan+cnt,y[i]) - lisan;
add(tx,ty,-sc[i],);
}
printf("%d\n",-solve());
}
return ;
}
/*
5 2
09:00:00 09:30:00 2
09:40:00 10:00:00 3
09:29:00 09:59:00 10
09:30:00 23:59:59 4
07:00:00 09:31:00 3
*/