http://poj.org/problem?id=1275
题目大意：
一商店二十四小时营业，但每个时间段需求的雇员数不同（已知，设为R[i]），现有n个人申请这份工作，其可以从固定时间t连续工作八个小时，问在满足需求的情况下最小需要多少个雇员。
思路：
挺难的。。看了别人的思路搞半天。。
设num[ i ]为i时刻能够开始工作的人数，x[ i ]为实际雇佣的人数，那么x[ I ]<=num[ I ]。 设r[ i ]为i时刻至少需要工作的人数，于是有如下关系：
x[ I-7 ]+x[ I-6 ]+…+x[ I ]>=r[ I ]
设s[ I ]=x[ 1 ]+x[ 2 ]…+x[ I ]，
得到
s[ I ]-s[ I-1 ]>=0 (0<=I<=23)
s[ I-1 ]-s[ I ]>=-num[ I ] (0<=I<=23)
s[ I ]-s[ I-8 ]>=r[ I ] (8<=I<=23)
s[ I ]-s[ I+16 ]>=r[ I ]-s[ 23 ] (0<=I<= 7)
这里出现了小的困难，我们发现以上式子并不是标准的差分约束系统，因为在最后一个式子中出现了三个未知单位。但是注意到其中跟随 I变化的只有两个，于是s[23]就变得特殊起来，看来是需要我们单独处理，于是我们把 s[ 23 ]当作已知量放在右边。
经过这样的整理，整个图就很容易创建了，将所有形如 A-B>=C 的式子 我们从节点B 引出一条有向边指向 A 边的权值为C （这里注意由于左右确定，式子又是统一的>=的不等式，所以A和B是相对确定的，边是一定是指向A的） ，图就建成了 。 最后枚举所有s[ 23 ]的可能值，对于每一个s[23]，我们都进行一次常规差分约束系统问题的求解，判断这种情况是否可行，如果可行求出需要的最优值，记录到Ans中，最后的Ans的值即为所求。
不过按上面的死活出不来。最后和别人一样下标都+1过了。。。。。不知道嘛状况。
还有要加上0->24的边（看POJ discuss的）
大牛解释如下：
为避免负数，时间计数1～24。令：
R[i] i时间需要的人数 （1<=i<=24）
T[i] i时间应聘的人数 （1<=i<=24）
x[i] i时间录用的人数 （0<=i<=24），其中令x[0]=0
再设s[i]=x[0]+x[1]+……+x[i] （0<=i<=24），
由题意，可得如下方程组：
(1) s[i]-s[i-8]>=R[i] (8<=i<=24)
(2) s[i]-s[16+i]>=R[i]-s[24] (1<=i<=7)
(3) s[i]-s[i-1]>=0 (1<=i<=24)
(4) s[i-1]-s[i]>=-T[i] (1<=i<=24)
这个差分约束有个特殊的地方，(2)的右边有未知数s[24]。
这时可以通过枚举s[24]=ans来判断是否有可行解。
即(2)变形为(2‘) s[i]-s[16+i]>=R[i]-ans (1<=i<=7)
再通过SPFA求解(1)(2‘)(3)(4)。
不过最后有可能出现这种情况：
(1)(2‘)(3)(4)虽然有解，但求出的s[24]小于代入(2‘)里的ans！
这时，显然得到的s[]不满足原来的(2)了（请仔细比较(2)与(2‘)）。
不过虽然得到的解不满足原方程组，但这并不代表(1)(2)(3)(4)在s[24]=ans时没有可行解！
此外，值得注意的是，当得到的s[24]>ans时，虽然s[24]不一定是最优解，但把ans置成s[24]后，确实是可行解。
所以，简单把(2)置换成(2‘)是有问题的！
为了等价原命题，必须再加上条件：s[24]>=ans
这就是所谓加出来的那条边（5） s[24]－s[0]>=ans
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int MAXN=23+10;
const int MAXM=3000;
const int INF=-9999999;
struct edge
{
int to;
int val;
int next;
}e[MAXM];
int head[MAXN],dis[MAXN],len,m;
int num[MAXN],r[MAXN];
void add(int from,int to,int val)
{
e[len].to=to;
e[len].val=val;
e[len].next=head[from];
head[from]=len++;
}
bool spfa(int k)
{
int start=0;
for(int i=0;i<=24;i++)
dis[i]=INF;
bool vis[MAXN]={0};
int cnt[MAXN]={0};
queue<int> q;
q.push(start);
vis[start]=1;
cnt[start]=1;
dis[start]=0;
while(!q.empty())
{
int cur=q.front();
q.pop();
vis[cur]=false;
for(int i=head[cur];i!=-1;i=e[i].next)
{
int id=e[i].to;
if(dis[id] < dis[cur] + e[i].val)
{
dis[id]=dis[cur] + e[i].val;
if(!vis[id])
{
if(++cnt[id] > 24)
return false;
vis[id]=true;
q.push(id);
}
}
}
}
if(k!= dis[24])
return false;
return true;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
memset(num,0,sizeof(num));
for(int i=1;i<=24;i++)
scanf("%d",&r[i]);
scanf("%d",&m);
for(int i=0;i<m;i++)
{
int t;
scanf("%d",&t);
num[t+1]++;
}
bool ok=false;
for(int k=0;k<=m;k++)
{
memset(head,-1,sizeof(head));
len=0;
add(0,24,k);
for(int i=1;i<=24;i++)
{
add(i-1,i,0);
add(i,i-1,-num[i]);
if(i>8)
add(i-8,i,r[i]);
else
add(i+16,i,r[i]-k);
}
if(spfa(k) )
{
ok=true;
break;
}
}
if(!ok)
puts("No Solution");
else
printf("%d\n",dis[24]);
}
return 0;
}