POJ_1275
对差分约束系统还是有点摸不着头脑的感觉，看了别人的分析之后才把代码写了出来。
首先这个题目可以做两个预处理，一个是在输入数据时找出R[i]的最大值，最后的结果一定是大于等于R[i]的，这样在枚举结果时就可以减少一部分工作量。另一个是在输入结束后，可以枚举8个小时的区间，如果这个区间里所有可雇用的人数加起来，还不足区间尾那个时间所需要的工人数，那么这种情况一定是无解的，反之，便一定是有解的。
如果设S[i]为[0,i)这些时间内雇佣的总人数，那么可以列出下面几个差分约束方程：
①S[i+1]-S[i]>=0；
②S[i]-S[i+1]>=-t[i]；
③0<=j<=24，i=(j+8)mod24，如果结果i为0，赋i值为24。
当i>j时，S[i]-S[j]>=R[i-1]；
当i<j时，S[i]-S[j]>=R[i-1]-sum；
④S[24]-S[0]>=sum。
之后，我们可以枚举sum的值，然后依据上面的四个条件建图，最后判断S[24]的值是否等于sum即可。在用SPFA的时候，还要注意对可能存在负圈的情况作出判断。
#include<stdio.h>
#include<string.h>
int R[30],d[30],t[30],first[30],next[120],v[120],w[120];
int q[900],inq[30],inedq[30];
int main()
{
int i,j,k,N,T,ok,tsum,sum,Rmax,u,e,front,rear;
scanf("%d",&T);
while(T--)
{
memset(t,0,sizeof(t));
Rmax=0;
for(i=0;i<24;i++)
{
scanf("%d",&R[i]);
if(R[i]>Rmax)
Rmax=R[i];
}
scanf("%d",&N);
for(i=0;i<N;i++)
{
scanf("%d",&k);
t[k]++;
}
ok=1;
for(i=0;i<24;i++)
{
tsum=0;
for(j=i,k=0;k<8;j--,k++)
{
if(j<0)
j+=24;
tsum+=t[j];
}
if(tsum<R[i])
{
ok=0;
break;
}
}
if(!ok)
{
printf("No Solution\n");
continue;
}
for(sum=Rmax;sum<=N;sum++)
{
e=0;
memset(first,-1,sizeof(first));
for(i=0;i<24;i++)
{
w[e]=0;
v[e]=i;
next[e]=first[i+1];
first[i+1]=e;
e++;
w[e]=t[i];
v[e]=i+1;
next[e]=first[i];
first[i]=e;
e++;
}
for(j=0;j<=24;j++)
{
i=(j+8)%24;
if(i==0)
i=24;
if(i>j)
w[e]=-R[i-1];
else
w[e]=sum-R[i-1];
v[e]=j;
next[e]=first[i];
first[i]=e;
e++;
}
w[e]=sum;
v[e]=24;
next[e]=first[0];
first[0]=e;
e++;
for(i=0;i<=24;i++)
{
inq[i]=0;
d[i]=10000;
inedq[i]=0;
}
d[0]=0;
front=rear=0;
q[rear++]=0;
ok=1;
while(front<rear)
{
u=q[front++];
inq[u]=0;
for(e=first[u];e!=-1;e=next[e])
if(d[u]+w[e]<d[v[e]])
{
d[v[e]]=d[u]+w[e];
if(!inq[v[e]])
{
q[rear++]=v[e];
inq[v[e]]=1;
if(++inedq[v[e]]>24)
{
d[24]=-1;
front=rear;
break;
}
}
}
}
if(d[24]==sum)
break;
}
printf("%d\n",sum);
}
return 0;
}