poj 3762 The Bonus Salary! 需離散化

點擊打開鏈接 The Bonus Salary! 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_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

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;
    queueq;
    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;
}
void end(int s,int t)
{
    int u, sum = inf;
    for(u=t; u!=s; u=pre[u])
    {
        sum = min(sum,Edge[path[u]].cap);
    }
    max_flow+=sum;                          //記錄最大流
    for(u = t; u != s; u=pre[u])
    {
        Edge[path[u]].cap -= sum;
        Edge[path[u]^1].cap += sum;
        ans += sum*Edge[path[u]].cost;     //  cost記錄的為單位流量費用，必須得乘以流量。
    }
}
int main()
{
    int n,k,s,t;
    scanf("%d%d",&n,&k);
    memset(head,-1,sizeof(head));
    memset(z,0,sizeof(z));
    NE=ans=max_flow=s=0;
    int num=0,h,m,ss;
    for(int i=0; i