记录编号	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;
}