POJ1275Cashier Employment（查分约束系统）

链接1275Cashier Employment

题目大意就是说有一些人来应聘一个超级市场的工作，每个人的应聘的起始时间在0~23时之间，而超市在时间i需要R[i]个工作人员，而每个人的工作时间都是8小时，问最少需要多少人使得超市一天24小时满足超市的工作人数的需要。

设工作时间为1~24时，S[i]表示前i个小时所需要的工作人数的最小值，那么结果就可以表示成0为起点，24为终点的最短路。下面是约束不等式：

0<=S[i] - S[i-1]<= t[i] (1<=i<=24)

S[i] - S[i-8] >= R[i] (8<=i<=24)

S[i] + S[24] - S[i+16] >= R[i] (0<=i<=7)

整理之后：

S[i] - S[i-1] >= 0 (1<=i<=24)

S[i-1] - S[i] >= -t[i] (1<=i<=24)

S[i] - S[i-8] >= R[i] (8<=i<=24)

S[i] - S[i+16] >= R[i] - S[24] (0<=i<=7)

这样按照A-B >= W就可以建一些由B指向A的权值为W的有向边，求最长路。

或则是A指向B的权值为-W的有向边，并求其最短路。

另外，由于上图中S[24]是不知道的，所以枚举它就行，我是二分枚举的。

数据比较水（只有24个小时），用Bellman-Ford即可：

  1 #include <map>
  2 #include <set>
  3 #include <stack>
  4 #include <queue>
  5 #include <cmath>
  6 #include <ctime>
  7 #include <vector>
  8 #include <cstdio>
  9 #include <cctype>
 10 #include <cstring>
 11 #include <cstdlib>
 12 #include <iostream>
 13 #include <algorithm>
 14 using namespace std;
 15 #define eps 1e-15
 16 #define MAXN  25
 17 #define INF 1000000007
 18 #define MAX(a,b) (a > b ? a : b)
 19 #define MIN(a,b) (a < b ? a : b)
 20 #define mem(a) memset(a,0,sizeof(a))
 21 
 22 struct EDGE
 23 {
 24     int v;
 25     int w;
 26     int next;
 27 }edge[3*MAXN];
 28 int head[MAXN], d[MAXN],tot,T,N,R[MAXN],t[MAXN],ans,x;
 29 
 30 bool Bellman_Ford(int s)
 31 {
 32     for(int i=0;i<=24;i++) d[i] == (i==s)?0:INF;
 33     for(int k=1;k<=24;k++)
 34     {
 35         for(int i=0;i<=24;i++)
 36         {
 37             for(int e = head[i];d[i]!=INF && e!=-1;e=edge[e].next)
 38             {
 39                 if(d[edge[e].v]>d[i]+edge[e].w)
 40                 {
 41                     d[edge[e].v] = d[i] + edge[e].w;
 42                 }
 43             }
 44         }
 45     }
 46     for(int i=0;i<=24;i++)
 47     {
 48         for(int e = head[i];d[i]!=INF && e!=-1;e=edge[e].next)
 49         {
 50             if(d[edge[e].v]>d[i]+edge[e].w)return false;
 51         }
 52     }
 53     return true;
 54 }
 55 
 56 void AddEdge(int u,int v,int w)
 57 {
 58     edge[tot].v = v;
 59     edge[tot].w = w;
 60     edge[tot].next = head[u];
 61     head[u] = tot++;
 62 }
 63 
 64 void BuildGragh(int NumOfPer)//由于每次总人数都不一样，所以需要重新建图
 65 {
 66     tot = 0;   mem(edge); memset(head,-1,sizeof(head));
 67     for(int i=1;i<=24;i++){AddEdge(i-1,i,t[i]); AddEdge(i,i-1,0);}
 68     for(int i=8;i<=24;i++) AddEdge(i,i-8,-R[i]);
 69     for(int i=0;i<=7;i++) AddEdge(i,i+16,NumOfPer-R[i]);
 70     AddEdge(24,0,-NumOfPer);
 71 }
 72 
 73 
 74 void BSearch(int low,int high)//对总人数二分
 75 {
 76     if(low > high)return ;
 77     int mid = (low + high) / 2;
 78     BuildGragh(mid);
 79     if(Bellman_Ford(0))//表示可以找到一种解决方案
 80     {
 81         ans = mid;
 82         BSearch(low, mid-1);
 83     }
 84     else
 85     {
 86         BSearch(mid+1,high);
 87     }
 88 }
 89 
 90 int main()
 91 {
 92     while(~scanf("%d", &T))while(T--)
 93     {
 94 
 95         mem(R);  mem(t);
 96         for(int i=1;i<=24;i++)
 97         {
 98             scanf("%d", &R[i]);
 99         }
100         scanf("%d", &N);
101         for(int i=0;i<N;i++){ scanf("%d", &x); t[x+1]++;}
102         ans = -1;
103         BSearch(1,N);
104         if(ans == -1) printf("No Solution
");
105         else printf("%d
",ans);
106     }
107     return 0;
108 }