/* s[]表示最优方案的序列中的前缀和，那么s[23]就是最优方案 由题意我们可以列出这样一些式子： s[i]+s[23]-s[16+i]>=a[i] (i-8<0) s[i]-s[i-8]>=a[i] (i-8>0)//这两个柿子选一个 b[i]>=s[i]-s[i-1]>=0 然后可以化简为： s[i]-s[16+i]>=a[i]-s[23] s[i]-s[i-8]>=a[i] s[i]-s[i-1]>=0 s[i-1]-s[i]>=-b[i] 这就满足了差分约束的形式了 呢么就让减数向被减数连一条边，权值就是不等式右边的常数 对于s[23]我们二分答案，因此就转化为对于一个既定的s[23]，以及按照一定规则建好的图，判断这个条件下是否存在负环 如果存在说明答案太小，如果不存在则答案合法，继续松弛 */#include #include #include #include #define maxn 30#define INF 10000000000using namespace std;int T,num;int s=24,vis[maxn],inq[maxn],head[maxn],dis[maxn],a[maxn],b[maxn];struct node{ int to,pre,v;}e[200];void Insert(int from,int to,int v){ e[++num].to=to; e[num].v=v; e[num].pre=head[from]; head[from]=num;}bool spfa(){ //判负环 for(int i=0;i
q; q.push(s); while(!q.empty()){ int u=q.front();q.pop(); inq[u]=0; if(vis[u]>25)return 0; for(int i=head[u];i;i=e[i].pre){ int v=e[i].to; if(dis[v]>=dis[u]+e[i].v)continue; dis[v]=dis[u]+e[i].v; vis[v]++; if(!inq[v])inq[v]=1,q.push(v); } } return 1;}bool check(int s0){ num=0;memset(head,0,sizeof(head)); for(int i=0;i<24;i++){ if(i>=8)Insert(i-8,i,a[i]); else Insert(i+16,i,a[i]-s0); if(i)Insert(i,i-1,-b[i]),Insert(i-1,i,0); else Insert(i,s,-b[i]),Insert(s,i,0); } Insert(23,s,-s0),Insert(s,23,s0); return spfa();}int main(){ freopen("cashier.in","r",stdin);freopen("cashier.out","w",stdout); scanf("%d",&T); while(T--){ int l=0,r=0; for(int i=0;i<24;i++)scanf("%d",&a[i]),l=max(l,a[i]); for(int i=0;i<24;i++)scanf("%d",&b[i]),r+=b[i]; if(l>r||!check(r)){puts("-1");continue;} if(l==0){puts("0");continue;} int ans; while(l<=r){ int mid=(l+r)>>1; if(check(mid))ans=mid,r=mid-1; else l=mid+1; } printf("%d\n",ans); }}