首页 > 代码库 > POJ1275出纳员的雇佣【差分约束】

POJ1275出纳员的雇佣【差分约束】

出纳员的雇佣

Tehran的一家每天24小时营业的超市,需要一批出纳员来满足它的需要。超市经理雇佣你来帮他解决问题:超市在每天的不同时段需要不同数目的出纳员(例如:午夜时只需一小批,而下午则需要很多)来为顾客提供优质服务。他希望雇佣最少数目的出纳员。
经理已经提供你一天的每一小时需要出纳员的最少数量——R(0), R(1), ..., R(23)。R(0)表示从午夜到上午1:00需要出纳员的最少数目,R(1)表示上午1:00到2:00之间需要的,等等。每一天,这些数据都是相同的。有N人申请这项工作,每个申请者I在24小时中,从一个特定的时刻开始连续工作恰好8小时,定义tI (0 <= tI <= 23)为上面提到的开始时刻。也就是说,如果第I个申请者被录取,他(她)将从tI 时刻开始连续工作8小时。
你将编写一个程序,输入R(I)(I = 0..23)和tI (I = 1..N),它们都是非负整数,计算为满足上述限制需要雇佣的最少出纳员数目。在每一时刻可以有比对应的R(I)更多的出纳员在工作。

输入格式:

输入文件的第一行为测试点个数(<= 20)。每组测试数据的第一行为24个整数表示R(0),R(1),..., R(23)(R(I)<= 1000)。接下来一行是N,表示申请者数目(0 <= N <= 1000),接下来每行包含一个整数tI (0 <= tI <= 23)。两组测试数据之间没有空行。

输出格式:

对于每个测试点,输出只有一行,包含一个整数,表示需要出纳员的最少数目。如果无解,你应当输出“No Solution!”

样例输入:

1
1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
5
0
23
22
1
10

样例输出:

1

时间限制:

1s
 
(先每个时间段加一以便C++操作)
差分约束:
0 <= S[i]-S[i-1]<=W[i];      // 雇佣的人数少于申请者但不能为负数
S[i]-S[i-8]>=R[i]               // 当i>=8时,该方程成立,否则将出现负数显然不成立
S[i+16]-S[i]<=x-R[i]   // 当i<8时,由于昨天的雇人可以通宵上班,因此这个约束通过反面处理
S[24] - S[0] >=x                     // 最后24小时内雇佣人应该大于等于x个人
S[i]-S[j]<=K 则从顶点j向i引一条权值为K的边。该系统是否成立也就在于是否存在负环,于是用SPFA判断负环。
然而x(也就是答案)未知,而x<=1000,所以可以二分查找找出最小的x。注意归零。
 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<queue>
 5 using namespace std;
 6 queue<int> Q;
 7 const int N=25;
 8 int R[N],W[N],dis[N],map[N][N],times[N];
 9 bool go[N][N],in[N];
10 bool SPFA(int x)
11 {
12     int tmp;
13     memset(dis,127,sizeof(dis));
14     memset(times,0,sizeof(times));
15     memset(map,0,sizeof(map));
16     memset(in,0,sizeof(in));
17     dis[24]=0;
18     times[24]=1;
19     for(int i=8;i<=24;i++) map[i][i-8]=-R[i];
20     for(int i=1;i<=7;i++) map[i][i+16]=x-R[i];
21     for(int i=1;i<=24;i++) map[i-1][i]=W[i];
22     map[24][0]=-x;
23     Q.push(24);
24     while(!Q.empty())
25     {
26         tmp=Q.front();
27         in[tmp]=0;
28         Q.pop();
29         for(int i=0;i<=24;i++) if(go[tmp][i]&&dis[i]>dis[tmp]+map[tmp][i])
30         {
31             dis[i]=dis[tmp]+map[tmp][i];
32             times[i]++;
33             if(!in[i])
34             {
35                 in[i]=1;
36                 Q.push(i);
37             }
38             if(times[i]>25) return false;
39         }
40     }
41     return (dis[0]==-x);
42 }
43 int main()
44 {
45     int lower,upper,t,n,x,mid;
46     bool flag;
47     for(int i=8;i<=24;i++) go[i][i-8]=1;
48     for(int i=1;i<=7;i++) go[i][i+16]=1;
49     for(int i=1;i<=24;i++) go[i][i-1]=go[i-1][i]=1;
50     go[24][0]=1;
51     scanf("%d",&t);
52     for(int z=1;z<=t;z++)
53     {
54         memset(W,0,sizeof(W));
55         for(int i=1;i<=24;i++) scanf("%d",&R[i]);
56         scanf("%d",&n);
57         for(int i=1;i<=n;i++)
58         {
59             scanf("%d",&x);
60             W[x+1]++;
61         }
62         lower=1;
63         upper=n;
64         flag=false;
65         while(lower<=upper)
66         {
67             mid=(lower+upper)>>1;
68             if(SPFA(mid))
69             {
70                 flag=true;
71                 upper=mid-1;
72             }
73             else lower=mid+1;
74         }
75         if(!flag) printf("No Solution\n");
76         else printf("%d\n",lower);
77     }
78 }

 

POJ1275出纳员的雇佣【差分约束】