记录编号	295803	评测结果	WWWWWWWWWW
题目名称	[POJ1275]出纳员的雇佣	最终得分	0
用户昵称	AntiLeaf	是否通过	未通过
代码语言	C++	运行时间	0.023 s
提交时间	2016-08-14 16:19:33	内存使用	0.29 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=30,maxe=110;
bool Bellman_Ford();
int T,n,m,k,x,s[maxe],t[maxe],w[maxe],dis[maxn];
int r[maxn],a[maxn],L,R,ans;
int main(){
#define MINE
#ifdef MINE
	freopen("cashieremployment.in","r",stdin);
	freopen("cashieremployment.out","w",stdout);
#endif
	scanf("%d",&T);
	while(T--){
		memset(a,0,sizeof(a));
		m=0;
		for(int i=1;i<=24;i++)scanf("%d",&r[i]);
		scanf("%d",&k);
		L=1;R=k;
		for(int i=1;i<=k;i++){
			scanf("%d",&x);
			a[x+1]++;
		}
		n=24;
		for(int i=0;i<n;i++){
			s[++m]=i;
			t[m]=i-1;
			w[m]=0;
			s[++m]=i-1;
			t[m]=i;
			w[m]=-a[i];
		}
		for(int i=8;i<n;i++){
			s[++m]=i;
			t[m]=i-8;
			w[m]=r[i];
		}
		x=m;
		while(L<=R){
			m=x;
			ans=(L+R)>>1;
			for(int i=0;i<8;i++){
				s[++m]=i;
				t[m]=i+16;
				w[m]=r[i]-ans;
			}
			s[++m]=24;
			t[m]=0;
			w[m]=ans;
			if(!Bellman_Ford()&&dis[24]==ans)R=ans-1;
			else L=ans+1;
		}
		if(L>k)printf("No Solution\n");
		else printf("%d\n",L);
	}
	return 0;
}
bool Bellman_Ford(){
	memset(dis,0,sizeof(dis));
	for(int k=1;k<n;k++)for(int i=1;i<=m;i++)
		dis[t[i]]=max(dis[t[i]],dis[s[i]]+w[i]);
	for(int i=1;i<=m;i++)if(dis[t[i]]<dis[s[i]]+w[i])return true;
	return false;
}