Teacher 2008-9-6 00:46
北大pku poj 3171 Cleaning Shifts解题报告源代码
题目地址: [url]http://acm.pku.edu.cn/JudgeOnline/problem?id=3171[/url]
-----代码仅供参考学习-----
Description
Farmer John's cows, pampered since birth, have reached new heights of fastidiousness. They
now require their barn to be immaculate. Farmer John, the most obliging of farmers, has no
choice but hire some of the cows to clean the barn.
Farmer John has N (1 <= N <= 10,000) cows who are willing to do some cleaning. Because dust
falls continuously, the cows require that the farm be continuously cleaned during the
workday, which runs from second number M to second number E during the day (0 <= M <= E <=
86,399). Note that the total number of seconds during which cleaning is to take place is E-
M+1. During any given second M..E, at least one cow must be cleaning.
Each cow has submitted a job application indicating her willingness to work during a certain
interval T1..T2 (where M <= T1 <= T2 <= E) for a certain salary of S (where 0 <= S <=
500,000). Note that a cow who indicated the interval 10..20 would work for 11 seconds, not
10. Farmer John must either accept or reject each individual application; he may NOT ask a
cow to work only a fraction of the time it indicated and receive a corresponding fraction of
the salary.
Find a schedule in which every second of the workday is covered by at least one cow and
which minimizes the total salary that goes to the cows.
Input
Line 1: Three space-separated integers: N, M, and E.
Lines 2..N+1: Line i+1 describes cow i's schedule with three space-separated integers: T1,
T2, and S.
Output
Line 1: a single integer that is either the minimum total salary to get the barn cleaned or
else -1 if it is impossible to clean the barn.
Sample Input
3 0 4
0 2 3
3 4 2
0 0 1
Sample Output
5
Hint
Explanation of the sample:
FJ has three cows, and the barn needs to be cleaned from second 0 to second 4. The first cow
is willing to work during seconds 0, 1, and 2 for a total salary of 3, etc.
Farmer John can hire the first two cows.
解题思路：
John根据给定的时间段雇佣cows来清理畜棚，而每个cow有自己的工作时间和所需工资。
题目是要求一种既能完成工作又是最小花销的方案（所付工资最少）。
把cow的工作时间段T1~T2，看成两点，这样工资可以看成两点之间边的权。于是问题可以抽象为单源
最短路径。----选择dijkstra算法。T1是边开始的顶点，T2为后一顶点。
应用dijkstra的过程中需要加一些处理，如题目sample中所说：he barn needs to be cleaned from
second 0 to second 4. The first cow is willing to work during seconds 0, 1, and 2 for..可以
将对应的边（T1,T2,S）修改为（T1,T2+1,S），这样就不需要加相邻边(T2,T2+1,0)。（因为总顶点数太
多了）
其中代码中的cmp1函数（for qsort），是根据cow开始工作的时间点排序，如果开始时间相同，则根
据结束时间排。
然后就是对dijkstra算法的实现。。。输出结果为d[e+1]，即源点道e+1距离（工资），如果其值为
INFINITY，说明没有所需方案，则输出-1。
#include<iostream>
using namespace std;
#define INFINITY 1000000
#define MAXE 86405
#define MAXN 20002
int n;
long m,e,d[MAXE];
long s[MAXE];
long p[MAXN];
struct cow{
long t1;
long t2;
long w;
}c[MAXN];
void dijkstra()
{
long i,j,min;
for(i=m;i<=e+1;i++)
d=INFINITY;
d[c[0].t1]=0;
j=0;
while(j<N)
{
min = d[c[j].t2];
for(i = s[c[j].t1]; i < s[c[j].t2]; i++)
if(min>d
+c[j].w)
min = d
+c[j].w;
d[c[j].t2] = min;
j++;
}
}
int cmp1(const void *a,const void *b)
{
if(((struct cow *)a)->t1==((struct cow *)b)->t1)
return ((struct cow *)a)->t2-((struct cow *)b)->t2;
return ((struct cow *)a)->t1-((struct cow *)b)->t1;
}
int cmp2(const void *a, const void *b)
{
return *(long *)a-*(long *)b;
}
int main()
{
int i,j;
scanf("%ld%ld%ld",&n,&m,&e);
memset(s,0,sizeof(s[0]));
for(i=0,j=0;i<N;I++)
{
scanf("%ld%ld%ld",&c.t1,&c.t2,&c.w);
c.t2++;
if(s[c.t1]==0)
{
p[j++]=c.t1;
s[c.t1]=1;
}
if(s[c.t2]==0)
{
p[j++]=c.t2;
s[c.t1]=1;
}
}
qsort(p,j,sizeof(p[0]),cmp2);
for(i=0;i<J;I++)
s
=i;
qsort(c,n,sizeof(c[0]),cmp1);
dijkstra();
if(d[e+1]==INFINITY)
printf("-1\n");
else
printf("%ld\n",d[e+1]);
return 0;
}