出纳员问题——差分约束系统，数学问题

出纳员问题——差分约束系统，数学问题"/>

出纳员问题——差分约束系统，数学问题

题目：/problem.php?id=1092

分析：

首先将时刻0~23改成1~24。原因在于便于处理s[1]与s[0]。

记x[i]为时刻i实际工作人数。

记s[i]=x[1]+x[2]+x[3]+...+x[i]。

记r[i]=R[i-1]，i=1~24。R[i]如题目定义。

记nm[i]为时刻i应聘的人数。

从而：

1、0<=x[i]=s[i]-s[i-]<=nm[i]      1<=i<=24

2、s[i]-s[i-8]>=r[i]     9<=i<=24

3、s[i]+s[24]-s[24-(8-i)]>=r[i]，即s[i]-s[16+i]>=r[i]-s[24]，因为此时不知道s[24]的值，从而s[24]记为ans，得到
      s[i]-s[16+i]>=r[i]-ans，1<=i<=8

     从0~n遍历ans，如果某个ans没有出现正环，即为答案，否则输出无解。

需要注意的是，上面1、2中的s[24]仍记作s[24]，不必换成ans。

4、s[24]-s[0]=ans。可写可不写。

AC代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
const int Maxn=48;
const int Mod=107;
int T,n,r[Maxn],s[Maxn],t,nm[Maxn];
int num,head[Maxn],deep[Maxn];
int hd=0,tl=1,que[4*Maxn],vis[Maxn];//采用循环队列 
int dis[Maxn];
struct Edge{int to,nxt,w;
}edge[4*Maxn];
void join(int from,int to,int w){edge[++num].nxt=head[from];edge[num].to=to;edge[num].w=w;head[from]=num;
}
void build_graph(int ans){num=0;memset(head,0,sizeof(head));//join(0,24,ans);//s[24]-s[0]=ans;for(int i=1;i<=24;i++){join(i-1,i,0);//s[i]-s[i-1]>=0join(i,i-1,-nm[i]);//s[i]-s[i-1]<=num[i],s[i-1]-s[i]>=-num[i]//nm[i]，i时刻可以提供的人数 }for(int i=9;i<=24;i++)join(i-8,i,r[i]);//s[i]-s[i-8]>=r[i]//r[i]，i时刻需要的人数 for(int i=1;i<=8;i++)join(i+16,i,r[i]-ans);//s[i]+s[24]-s[24-(8-i)]>=r[i]，即s[i]-s[i+16]>=r[i]-s[24]	    						
}
bool spfa(){   for(int i=0;i<=24;i++){dis[i]=-1e9;vis[i]=0;}hd=0;//初始化 tl=1;que[1]=0;//以0为起点 dis[0]=0;vis[0]=1;deep[0]=1;while(hd!=tl){hd=hd%Mod+1;int from=que[hd];vis[from]=0;for(int i=head[from];i;i=edge[i].nxt){int to=edge[i].to;int w=edge[i].w;if(dis[to]<dis[from]+w){//取大 dis[to]=dis[from]+w;deep[to]=deep[from]+1;if(deep[to]>24)return 0;if(!vis[to]){tl=tl%Mod+1;que[tl]=to;vis[to]=1;}}}   }return 1;
}
int main(){freopen("Cashier0.in","r",stdin);cin>>T;while(T--){for(int i=1;i<=24;i++)//改时刻0-23为1-24，便于处理s[1] scanf("%d",&r[i]);cin>>n;memset(nm,0,sizeof(nm));for(int j=1;j<=n;j++){scanf("%d",&t);nm[t+1]++;//改时刻0-23为1-24 }bool flg=0;for(int ans=0;ans<=n;ans++){build_graph(ans);if(spfa()){printf("%d\n",ans);flg=1;break;}}if(!flg)printf("No Solution\n");}return 0;
}