Language: Default The Bonus Salary!
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 Sample Output Hint The optimal strategy is: Day1: Task1, Task 4 Day2: Task 3 The total productivity score is 2 + 4 + 10 = 16. Source |
题意:有n个任务要在k天时间内选部分完成,每个任务在每天有一个规定的时间,必须要在这个时间内做这个任务,完成一个任务会得到相应的分数,问能得到的最大分数是多少。
思路:离散化+最小费用流,这一题和poj3680是一样的,先对时间离散化,然后添加源点S和汇点T,1->2,2->3,3->4.......T-1->T这样连边,容量为k,费用为0,对于每个任务起始时间u->v连边,容量为1,费用为-w。
代码:
#include <iostream>
#include <functional>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <queue>
#pragma comment (linker,"/STACK:102400000,102400000")
#define pi acos(-1.0)
#define eps 1e-6
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define FRE(i,a,b) for(i = a; i <= b; i++)
#define FREE(i,a,b) for(i = a; i >= b; i--)
#define FRL(i,a,b) for(i = a; i < b; i++)
#define FRLL(i,a,b) for(i = a; i > b; i--)
#define mem(t, v) memset ((t) , v, sizeof(t))
#define sf(n) scanf("%d", &n)
#define sff(a,b) scanf("%d %d", &a, &b)
#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)
#define pf printf
#define DBG pf("Hi\n")
typedef long long ll;
using namespace std;
#define INF 0x3f3f3f3f
#define mod 1000000009
const int maxn = 1005;
const int MAXN = 4050;
const int MAXM = 200010;
struct Line
{
int a,b,w;
}line[MAXN/2];
struct Edge
{
int to,next,cap,flow,cost;
}edge[MAXM];
int head[MAXN],tol;
int pre[MAXN],dis[MAXN];
bool vis[MAXN];
int N,n,k;
int a[MAXN],cnt;
void init(int n)
{
N=n;
tol=0;
memset(head,-1,sizeof(head));
}
void addedge(int u,int v,int cap,int cost)
{
edge[tol].to=v;
edge[tol].cap=cap;
edge[tol].cost=cost;
edge[tol].flow=0;
edge[tol].next=head[u];
head[u]=tol++;
edge[tol].to=u;
edge[tol].cap=0;
edge[tol].cost=-cost;
edge[tol].flow=0;
edge[tol].next=head[v];
head[v]=tol++;
}
bool spfa(int s,int t)
{
queue<int>q;
for (int i=0;i<N;i++)
{
dis[i]=INF;
vis[i]=false;
pre[i]=-1;
}
dis[s]=0;
vis[s]=true;
q.push(s);
while (!q.empty())
{
int u=q.front();
q.pop();
vis[u]=false;
for (int i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].to;
if (edge[i].cap > edge[i].flow && dis[v] > dis[u] + edge[i].cost)
{
dis[v]=dis[u] + edge[i].cost;
pre[v]=i;
if (!vis[v])
{
vis[v]=true;
q.push(v);
}
}
}
}
if (pre[t]==-1) return false;
else return true;
}
//返回的是最大流,cost存的是最小费用
int minCostMaxflow(int s,int t,int &cost)
{
int flow=0;
cost=0;
while (spfa(s,t))
{
int Min=INF;
for (int i=pre[t];i!=-1;i=pre[edge[i^1].to])
{
if (Min > edge[i].cap-edge[i].flow)
Min=edge[i].cap-edge[i].flow;
}
for (int i=pre[t];i!=-1;i=pre[edge[i^1].to])
{
edge[i].flow+=Min;
edge[i^1].flow-=Min;
cost+=edge[i].cost*Min;
}
flow+=Min;
}
return flow;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("C:/Users/lyf/Desktop/IN.txt","r",stdin);
#endif
int i,j,h,m,s;
while (~scanf("%d%d",&n,&k))
{
cnt=0;
for (i=1;i<=n;i++)
{
scanf("%d:%d:%d",&h,&m,&s);
line[i].a=h*3600+m*60+s;
a[++cnt]=line[i].a;
scanf("%d:%d:%d",&h,&m,&s);
line[i].b=h*3600+m*60+s;
a[++cnt]=line[i].b;
scanf("%d",&line[i].w);
}
sort(a+1,a+1+cnt);
cnt=unique(a+1,a+1+cnt)-a-1;
init(cnt+2);
int S=0,T=cnt+1;
for (i=0;i<=cnt;i++)
addedge(i,i+1,k,0);
for (i=1;i<=n;i++)
{
int u=lower_bound(a+1,a+1+cnt,line[i].a)-a;
int v=lower_bound(a+1,a+1+cnt,line[i].b)-a;
addedge(u,v,1,-line[i].w);
}
int ans,cost;
ans=minCostMaxflow(S,T,cost);
printf("%d\n",-cost);
}
return 0;
}