 /**//*
題意:1天24小時,每個小時需要售貨員人r[i]個
n個工人應(yīng)聘,每個人開始工作時間為s[i],都工作8個小時
問最少的應(yīng)聘人數(shù)
設(shè)x[i]為前i個小時實際招聘的人數(shù),則x[0]=0,x[24]為所求
t[i]表示第i小時能招聘的人數(shù),則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]未知,二分枚舉這個值然后構(gòu)圖
用spfa判是否有環(huán),還有是否dist[24]==x24


差分約束需要是x-y,沒有x+y的
為了用到減號,一般都是設(shè)x[i]為前i個的,然后利用區(qū)間減法來滿足條件
最后用spfa判環(huán)或求最長(短)路

*/
#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);//邊權(quán)可以為負,所以賦為-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
搜索
最新評論

|
|