记录编号 |
156939 |
评测结果 |
AAAAAAAAAA |
题目名称 |
[POJ1275]出纳员的雇佣 |
最终得分 |
100 |
用户昵称 |
水中音 |
是否通过 |
通过 |
代码语言 |
C++ |
运行时间 |
0.012 s |
提交时间 |
2015-04-06 21:00:10 |
内存使用 |
0.32 MiB |
显示代码纯文本
#include<iostream>
#include<cstdio>
using namespace std;
int n,m,i,p,zj1,sj,L,R,mid,T,ans;
int dis[30],cnt[30],r[30],t[30];
const int INF=1e9;
int to[100]={0},head[30]={0},he[30]={0},ne[100]={0},w[100]={0};
inline void addedge(int u,int v,int c)
{to[++sj]=v,ne[sj]=head[u],head[u]=sj,w[sj]=c;}
int que[100]={0},qhead=1,qtail=99,qnum=0;bool flag[100]={0};
inline int GET()
{int x=que[qhead];if(++qhead==100)qhead=1;qnum--;flag[x]=0;return x;}
inline void PUSH_fr(int x)
{flag[x]=1,qnum++;if(!(--qhead))qhead=99;que[qhead]=x;}
inline void PUSH_be(int x)
{flag[x]=1,qnum++;if(++qtail==100)qtail=1;que[qtail]=x;}
inline bool spfa()
{
for(i=0;i<=24;i++)dis[i]=-INF,cnt[i]=0;
cnt[0]=1;PUSH_be(0);dis[0]=0;
while(qnum)for(zj1=GET(),i=head[zj1];i;i=ne[i])
if(dis[to[i]]<dis[zj1]+w[i])
{
dis[to[i]]=dis[zj1]+w[i];
if(!flag[to[i]])
{
if(++cnt[to[i]]>24)return 0;
if(qnum&&dis[que[qhead]]<=dis[to[i]])PUSH_fr(to[i]);
else PUSH_be(to[i]);
}
}
if(dis[24]==mid)return 1;
return 0;
}
int main()
{
freopen("cashieremployment.in","r",stdin);
freopen("cashieremployment.out","w",stdout);
scanf("%d",&T);
while(T--)
{
for(i=1;i<=24;i++)scanf("%d",r+i);
for(i=0;i<=24;i++)t[i]=head[i]=0;
scanf("%d",&n);sj=0;
for(i=1;i<=n;i++)scanf("%d",&zj1),t[zj1+1]++;
for(i=1;i<=24;i++)addedge(i-1,i,0),addedge(i,i-1,-t[i]);
for(i=0;i<=24;i++)he[i]=head[i];
ans=-1;L=0,R=n;
while(L<=R)
{
mid=(L+R)>>1;sj=48;
for(i=0;i<=24;i++)head[i]=he[i];
addedge(0,24,mid);
for(i=1;i<=8;i++)addedge(i+16,i,r[i]-mid);
for(i=9;i<=24;i++)addedge(i-8,i,r[i]);
if(spfa())ans=mid,R=mid-1;
else L=mid+1;
}
if(ans==-1)printf("No Solution\n");
else printf("%d\n",ans);
}
return 0;
}