題干：

A supermarket in Tehran is open 24 hours a day every day and needs a number of cashiers to fit its need. The supermarket manager has hired you to help him, solve his problem. The problem is that the supermarket needs different number of cashiers at different times of each day (for example, a few cashiers after midnight, and many in the afternoon) to provide good service to its customers, and he wants to hire the least number of cashiers for this job.?

The manager has provided you with the least number of cashiers needed for every one-hour slot of the day. This data is given as R(0), R(1), ..., R(23): R(0) represents the least number of cashiers needed from midnight to 1:00 A.M., R(1) shows this number for duration of 1:00 A.M. to 2:00 A.M., and so on. Note that these numbers are the same every day. There are N qualified applicants for this job. Each applicant i works non-stop once each 24 hours in a shift of exactly 8 hours starting from a specified hour, say ti (0 <= ti <= 23), exactly from the start of the hour mentioned. That is, if the ith applicant is hired, he/she will work starting from ti o'clock sharp for 8 hours. Cashiers do not replace one another and work exactly as scheduled, and there are enough cash registers and counters for those who are hired.

You are to write a program to read the R(i) 's for i=0..23 and ti 's for i=1..N that are all, non-negative integer numbers and compute the least number of cashiers needed to be employed to meet the mentioned constraints. Note that there can be more cashiers than the least number needed for a specific slot.?

Input

The first line of input is the number of test cases for this problem (at most 20). Each test case starts with 24 integer numbers representing the R(0), R(1), ..., R(23) in one line (R(i) can be at most 1000). Then there is N, number of applicants in another line (0 <= N <= 1000), after which come N lines each containing one ti (0 <= ti <= 23). There are no blank lines between test cases.

Output

For each test case, the output should be written in one line, which is the least number of cashiers needed.?
If there is no solution for the test case, you should write No Solution for that case.?

Sample Input

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

Sample Output

1

題目大意：

一句話題意：

在一家超市里，每個時刻都需要有營業員看管，R(i) (0 <= i < 24)表示從i時刻開始到i+1時刻結束需要的營業員的數目，現在有N(N <= 1000)個申請人申請這項工作，并且每個申請者都有一個起始工作時間 ti，如果第i個申請者被錄用，那么他會從ti時刻開始連續工作8小時。現在要求選擇一些申請者進行錄用，使得任何一個時刻i，營業員數目都能大于等于R(i)。求出至少需要錄用多少營業員。

解題報告：

? 考慮差分約束。

設??代表第(i-1)時這個時刻來應聘工作的人數，為這個時間段至少需要的人數，?為在第(i-1)時這個時刻招到的人數。

根據題意需要滿足：

0 <= has[i] <= num[i]

has[i] + has[i-1] + …+ has[i-7] >= r[i] （當然遇到i-7小于0的要處理一下）（題目中的連續工作8小時）

但是考慮到不方便建圖，重新定義關系：s[i] = has[1] + has[2] + … + has[i]

然后創建出滿足題目關系的圖：

s[i] -?s[i-1] >= 0

s[i] - s[i-1] <= num[i]

s[i] -?s[i-8] >= r[i]? ?(其中8 <= i <= 24)

s[i] + s[24] -?s[i+16] >= r[i]? (其中1 <=?i <= 7)

然后發現最后一個式子有三個參數了，但是還好s[24]是個常量，雖然不是常量(因為也屬于約束系統的)但是最起碼可以是個常量（大概因為他不帶 i ？）所以我們可以欽點這個常數的大小。然后看能否構造出滿足條件的解就可以了。

? ?當然指定s[24]了之后還要加上s[24]?= ans，又因為指定了s[0]=0，所以可以構造s[24]-s[0]=ans。然后題目是求最小值，即求最長路，以0為源點就可以了。又因為這題顯然是符合單調性的，所以對這個ans可以二分。

注意一個地方，那就是不能直接不加??s[24]?= ans 這個條件，然后直接檢測spfa之后的dis[24]<=ans，如果成立則移動r，不成立則移動l。這樣是不對的。

因為這樣相當于你先假設了s[24]來約束了s[1]~s[7]，然后構造出了一個有解的系統，然后檢查dis[24]，這時候如果dis[24]<ans，則說明說明你在假設了一個綜合的前提下得到了更小的解，但是這個解是在假設s[24]的前提下的，你此時因為ans就是s[24]，你此時s[24]>dis[24]說明，你在求解的過程中擴大了求解范圍（也就是削弱了約束），因為你輸入的條件是ans的，結果你現在得到的是小于ans的數，所以你把當前dis[24]帶入的雖然是你輸入的約束系統的合法解，但未必是符合題意的合法解。也就是dis[24]<ans成立，但是未必dis[24]人為放大到=ans也是成立的，但你輸入系統的時候要求dis[24]是ans，所以這樣是不可行的。

那有同學就會說，那spfa完后檢查dis[24]==ans不就好了？這樣也有個問題：就是dis[24]代表的是24號點取最小的時候構成的解，因為你差分約束系統只能求出一組解來不能求出全部解，也不能求出所有最優解，只能求出對于某個點來說的最優解，而此時構造出的s數組對于其他點來說未必是最優解。所以你dis[24]==24成立則肯定沒問題，但是dis[24]!=24也不代表就一定不成立。以為可能通過dis[24]變小一丟丟，就可能存在了合法解。我也不知道我上面在說什么，反正大概就是，假設你枚舉到一個正確答案ans，輸入到差分約束系統，但是你spfa出來可能dis[24]<ans，因為你ans輸入了一個比較大的范圍，我在這里面可能dis[24]可以取到一個比較小的值，但是dis[24]真取到這個小的值的時候雖然是約束系統的合法解，但是不是題意的合法解（其實我是怎么發現這一點的呢？就是你按照正確的方式建圖，然后找到答案了之后，對這個答案用錯誤的建圖方式但是用dis[24]<=ans去檢驗，也可以AC）。? emmm怎么說呢就是可以理解成：雖然分開看都可以成立，但是不代表他倆可以同時成立。所以解決辦法就是加上一個 s[24]=ans 這個約束，然后直接看有無解就可以了（這里就是有無正環）

總的來說：如果<ans來判斷會使得求得的答案<正確答案（即求出了看似正確的解但是不是正確的解）

如果用=ans來判斷，會使得求得的答案>正確答案（即本身可以是正確的解，但是通過你的判斷方法得出這個解是不成立的）

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<stack> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define F first #define S second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 2e5 + 5; const int INF = 0x3f3f3f3f; struct Edge {int ne,v,w; } e[MAX]; int tot,n; int head[MAX]; void add(int u,int v,int w) {e[++tot].v = v;e[tot].w = w;e[tot].ne = head[u];head[u] = tot; } int dis[MAX],cnt[MAX],vis[MAX];int spfa(int st) {for(int i = 0; i<=1231; i++) dis[i] = -INF; memset(vis,0,sizeof vis);memset(cnt,0,sizeof cnt);queue<int> q;dis[st]=0;q.push(st);vis[st]=1;cnt[st]=1;while(q.size()) {int cur = q.front(); q.pop();vis[cur]=0;for(int i = head[cur]; ~i; i = e[i].ne) {int v = e[i].v;if(dis[v] >= dis[cur] + e[i].w) continue;dis[v] = dis[cur] + e[i].w;if(!vis[v]) {cnt[v]++;vis[v]=1;q.push(v);if(cnt[v] > n) return 99999999;}}}return dis[24]; } int R[26],num[26]; int main() {int t;cin>>t;while(t--) {tot=0;memset(head,-1,sizeof head);for(int i = 1; i<=24; i++) scanf("%d",R+i),num[i]=0;scanf("%d",&n);for(int x,i = 1; i<=n; i++) scanf("%d",&x),num[x+1]++;int l = 0,r = n,mid,ans=-1;while(l<=r) {mid=(l+r)>>1;tot=0;memset(head,-1,sizeof head);for(int i = 1; i<=24; i++) add(i-1,i,0),add(i,i-1,-num[i]);for(int i = 9; i<=24; i++) add(i-8,i,R[i]);for(int i = 1; i<=8; i++) add(i+16,i,R[i] - mid);add(0,24,mid); add(24,0,-mid);if(spfa(0) == mid) ans = mid,r = mid - 1;else l = mid + 1; }if(ans == -1) printf("No Solution\n");else printf("%d\n",ans);}return 0 ; }

?

總結

以上是生活随笔為你收集整理的【POJ - 1275】Cashier Employment（差分约束，建图）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。