POJ 3762 The Bonus Salary! 离散 + 费用流

The Bonus Salary!

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_L_i : mm_L_i : ss_L_i to hh_R_i : mm_R_i : ss_R_i.
- 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_L_i:mm_L_i:ss_L_i hh_R_i:mm_R_i:ss_R_i w

Which means, the i-th task must be done from hh_L_i : mm_L_i : ss_L_i to hh_R_i : mm_R_i : ss_R_i and its productivity score is w. (0 ≤hh_L_i, hh_R_i ≤ 23, 0 ≤mm_L_i, mm_R_i, ss_L_i, ss_R_i ≤ 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_R_i : mm_R_i : ss_R_i is strictly later than hh_L_i : mm_L_i : ss_L_i.　

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

Hint

The optimal strategy is:
Day1: Task1, Task 4
Day2: Task 3
The total productivity score is 2 + 4 + 10 = 16.

题目大意：给你n个时间段，每个时间段都有一个权值，k天的选择限制，每个时间段只能选择一次，其中同一天能选择互不重叠的时间段，最多选择k天。问怎样选择使得总权值和最大。

题目分析：就是区间K覆盖问题，解法同POJ 3680 Intervals 离散 + 费用流，首先，先对区间的端点进行离散化，之后对每个区间的左端点u和右端点v建边（u，v，1，-w），再对每个坐标点 i 建边（i，i + 1，k，0），设离散后最大的点的坐标为x，建立源汇点s = 0， t = x + 1，建边（x，t，1，0）。跑一次最小费用最大流，结果即花费的相反数。

代码如下：

#include <stdio.h>
#include <string.h>
#include <algorithm>
#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
", -MCMF());
}
int main(){
    while(~scanf("%d%d", &n, &m)) work();
    return 0;
}

POJ 3762