| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 2321 | Accepted: 606 |
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 209:00:00 09:30:00 209:40:00 10:00:00 309:29:00 09:59:00 1009:30:00 23:59:59 407:00:00 09:31:00 3
Sample Output
16
Hint
The optimal strategy is:
Day1: Task1, Task 4Day2: Task 3The total productivity score is 2 + 4 + 10 = 16.题目大意：给你n个时间段，每个时间段都有一个权值，k天的选择限制，每个时间段只能选择一次，其中同一天能选择互不重叠的时间段，最多选择k天。问怎样选择使得总权值和最大。
题目分析：就是区间K覆盖问题，解法同，首先，先对区间的端点进行离散化，之后对每个区间的左端点u和右端点v建边（u，v，1，-w），再对每个坐标点 i 建边（i，i + 1，k，0），设离散后最大的点的坐标为x，建立源汇点s = 0， t = x + 1，建边（x，t，1，0）。跑一次最小费用最大流，结果即花费的相反数。
代码如下：
#include#include #include #define min(a, b) ((a) < (b) ? (a) : (b))#define REP(i, n) for(int i = 0; i < n; ++i)#define MS0(X) memset(X, 0, sizeof X)#define MS1(X) memset(X, -1, sizeof X)using namespace std;const int maxE = 1000000;const int maxN = 5000;const int maxM = 2014;const int oo = 0x3f3f3f3f;struct Edge{ int v, c, w, n;};Edge edge[maxE];int adj[maxN], l;int d[maxN], cur[maxN], Minflow;int inq[maxN], Q[maxE], head, tail;int cost, flow, s, t;int n, m, cnt;struct Node{ int l, r, w;}a[maxN];int b[maxN];void addedge(int u, int v, int c, int w){ edge[l].v = v; edge[l].c = c; edge[l].w = w; edge[l].n = adj[u]; adj[u] = l++; edge[l].v = u; edge[l].c = 0; edge[l].w = -w; edge[l].n = adj[v]; adj[v] = l++;}int SPFA(){ memset(d, oo, sizeof d); memset(inq, 0, sizeof inq); head = tail = 0; d[s] = 0; Minflow = oo; cur[s] = -1; Q[tail++] = s; while(head != tail){ int u = Q[head++]; inq[u] = 0; for(int i = adj[u]; ~i; i = edge[i].n){ int v = edge[i].v; if(edge[i].c && d[v] > d[u] + edge[i].w){ d[v] = d[u] + edge[i].w; cur[v] = i; Minflow = min(edge[i].c, Minflow); if(!inq[v]){ inq[v] = 1; Q[tail++] = v; } } } } if(d[t] == oo) return 0; flow += Minflow; cost += Minflow * d[t]; for(int i = cur[t]; ~i; i = cur[edge[i ^ 1].v]){ edge[i].c -= Minflow; edge[i ^ 1].c += Minflow; } return 1;}int MCMF(){ flow = cost = 0; while(SPFA()); return cost;}void work(){ int hh, mm, ss, ww, cnt1; MS1(adj); l = 0; cnt = 0; REP(i, n){ scanf("%d:%d:%d", &hh, &mm, &ss); a[i].l = hh * 3600 + mm * 60 + ss; scanf("%d:%d:%d", &hh, &mm, &ss); a[i].r = hh * 3600 + mm * 60 + ss; scanf("%d", &a[i].w); } REP(i, n){ b[cnt++] = a[i].l; b[cnt++] = a[i].r; } sort(b, b + cnt); cnt1 = 0; REP(i, cnt) if(i && b[i] != b[cnt1]) b[++cnt1] = b[i]; cnt = ++cnt1; REP(i, n) REP(j, cnt) if(a[i].l == b[j]){ a[i].l = j; break; } REP(i, n) REP(j, cnt) if(a[i].r == b[j]){ a[i].r = j; break; } s = 0; t = cnt; REP(i, n) addedge(a[i].l, a[i].r, 1, -a[i].w); REP(i, cnt) addedge(i, i + 1, m, 0); printf("%d\n", -MCMF());}int main(){ while(~scanf("%d%d", &n, &m)) work(); return 0;}