| 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:
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天的时间，问最多能够得到多少分。//2404K 1266MS
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cstdio>
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<int>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;
}
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<n; i++)
{
scanf("%d:%d:%d",&h,&m,&ss);
time[i].s=h*3600+m*60+ss;
z[num++]=time[i].s;
scanf("%d:%d:%d",&h,&m,&ss);
time[i].e=h*3600+m*60+ss;
z[num++]=time[i].e;
scanf("%d",&time[i].w);
}
sort(z,z+num);
int e=1;
memset(vist,0,sizeof(vist));
for(int i=0; i<num; i++)
if(!vist[z[i]])vist[z[i]]=e++;
for(int i=1; i<e-1; i++)
addEdge(i,i+1,inf,0);
for(int i=0; i<n; i++)
addEdge(vist[time[i].s],vist[time[i].e],1,-time[i].w);
addEdge(0,1,k,0);
t=e-1;
while(SPFA(s,t))
{
end(s,t);
}
printf("%d\n",-ans);
return 0;
}
poj 3762 The Bonus Salary! 需离散化,布布扣,bubuko.com
poj 3762 The Bonus Salary! 需离散化
原文：http://blog.csdn.net/crescent__moon/article/details/24551469