出纳员问题——差分约束系统,数学问题
题目:/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;
}
出纳员问题——差分约束系统,数学问题
题目:/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;
}
发布评论