| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 2299 | Accepted: 601 |
Description
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 than hh_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.
Source
有n个任务，每个任务都有一个区间，每完成一个任务就会得到一定的分数，每次只能做一个任务，而且要求做满此任务的整个时间段，给你k天的时间，问最多能够得到多少分。 首先时间太杂，因此需要离散化一下，将所有的时间点按照从小到大排序，然后每个时间点和它后面的时间点相连，容量为inf，费用为0.之所以这样连，是因为如果你要做这个时间点上的任务，那你就走时间段那条边，但如果你不做这个时间点上的任务，为了确保你还可以沿着时间继续走下去，所以建了一条容量为无穷费用为零的边。 将每个任务的开始和结束相连，容量为1，费用为负的分数，因为任务只能 做一次，且要求最大分数，所以分数为负。 源点与第一个时间点相连，容量为k，费用为0.表示一共有k天。//2404K 1266MS #include#include #include #include #include using namespace std; const int MAXN=100000; const int inf=10000000; int pre[MAXN]; // pre[v] = k：在增广路上，到达点v的边的编号为k int dis[MAXN]; // dis[u] = d：从起点s到点u的路径长为d int vis[MAXN]; // inq[u]：点u是否在队列中 int path[MAXN]; int head[MAXN]; int NE,tot,ans,max_flow; int z[90000]; int vist[MAXN]; struct T { int s,e,w; } time[2207]; struct node { int u,v,cap,cost,next; } Edge[MAXN]; void addEdge(int u,int v,int cap,int cost) { Edge[NE].u=u; Edge[NE].v=v; Edge[NE].cap=cap; Edge[NE].cost=cost; Edge[NE].next=head[u]; head[u]=NE++; Edge[NE].v=u; Edge[NE].u=v; Edge[NE].cap=0; Edge[NE].cost=-cost; Edge[NE].next=head[v]; head[v]=NE++; } int SPFA(int s,int t) // 源点为0，汇点为sink。 { int i; for(i=s; i<=t; i++) dis[i]=inf; memset(vis,0,sizeof(vis)); memset(pre,-1,sizeof(pre)); dis[s] = 0; queue q; q.push(s); vis[s] =1; while(!q.empty()) // 这里最好用队列，有广搜的意思，堆栈像深搜。 { int u =q.front(); q.pop(); for(i=head[u]; i!=-1; i=Edge[i].next) { int v=Edge[i].v; if(Edge[i].cap >0&& dis[v]>dis[u]+Edge[i].cost) { dis[v] = dis[u] + Edge[i].cost; pre[v] = u; path[v]=i; if(!vis[v]) { vis[v] =1; q.push(v); } } } vis[u] =0; } if(pre[t]==-1) return 0; return 1; }