/**//* 题意: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
搜索
最新评论
|
|