 /**//*
题意:1天24小时,每个小时需要售货员人r[i]个
n个工人应聘,每个人开始工作时间为s[i],都工作8个小时
问最少的应聘人数
设x[i]为前i个小时实际招聘的人数,则x[0]=0,x[24]为所求
t[i]表示第i小时能招聘的人数,则0<=x[i]-x[i-1]<=t[i]
同时,x[i]-x[i-8]>=r[i],由于可以跨越一天,把这个不等式再细分
x[i]-x[i-8]>=r[i] i>=9
x[24]+x[i]-x[i-8+24]>=r[i] i<=8
由于x[24]未知,二分枚举这个值然后构图
用spfa判是否有环,还有是否dist[24]==x24


差分约束需要是x-y,没有x+y的
为了用到减号,一般都是设x[i]为前i个的,然后利用区间减法来满足条件
最后用spfa判环或求最长(短)路

*/
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>

using namespace std;

const int MAXN = 30;
const int INF = 1000000000;

bool in[MAXN];
int cnt[MAXN],dist[MAXN];
int r[MAXN],t[MAXN];
vector<pair<int,int> > E[MAXN];

void reset(int x24)
  {
for(int i=0;i<=24;i++)
E[i].clear();
// 0<=x[i]-x[i-1]<=t[i]
for(int i=1;i<=24;i++)
 {
E[i-1].push_back(make_pair(i,0));
E[i].push_back(make_pair(i-1,-t[i]));
}
//x[24]+x[i]-x[i-8+24]>=r[i]
for(int i=1;i<=8;i++)
E[i-8+24].push_back(make_pair(i,r[i]-x24));
//x[i]-x[i-8]>=r[i]
for(int i=9;i<=24;i++)
E[i-8].push_back(make_pair(i,r[i]));
//x[24]-x[0]>=x[24]
E[0].push_back(make_pair(24,x24));
}

bool spfa(int x24)
  {
fill(dist,dist+25,-INF);//边权可以为负,所以赋为-INF
fill(in,in+25,false);
fill(cnt,cnt+25,0);
in[0]=1;
dist[0]=0;
cnt[0]=1;
queue<int>Q;
Q.push(0);
while(!Q.empty())
 {
int u=Q.front();Q.pop();
in[u]=false;
for(vector<pair<int,int> >::iterator it=E[u].begin();it!=E[u].end();it++)
 {
if(dist[it->first]<dist[u]+it->second)
 {
dist[it->first]=dist[u]+it->second;
if(in[it->first]==false)
 {
if(++cnt[it->first]>25)return false;
in[it->first]=true;
Q.push(it->first);
}
}
}
}
return dist[24]==x24;
}
int main()
  {
//freopen("in","r",stdin);
int T,n;
for(scanf("%d",&T);T--;)
 {
for(int i=1;i<=24;i++)
 {
scanf("%d",&r[i]);
t[i]=0;
}
scanf("%d",&n);
for(int i=1,x;i<=n;i++)
 {
scanf("%d",&x);
t[x+1]++;
}
int left=0,right=n+1;
while(right-left>1)
 {
int mid=(left+right)>>1;
reset(mid);
if(spfa(mid))right=mid;
else left=mid;
}
if(right==n+1)puts("No Solution");
else printf("%d\n",right);
}
return 0;
}
|
|
常用链接
随笔分类
Links
搜索
最新评论

|
|