对于两个变量的,可以枚举一个变量,本题刚刚枚举的变量就是答案,对于枚举变量,要用约束加边,如果直接将该位置的dis设为常数,其他的跟她有关的可能就不是一格差分条件。
#include<bits/stdc++.h> using namespace std; const int N=1e5+10; int r[25]; int num[N]; int h[N],ne[N],e[N],w[N],idx; int st[N],dis[N],cnt[N]; void add(int a,int b,int c){ e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++; } void build(int x){ int i; idx=0; memset(h,-1,sizeof h); for(i=1;i<=7;i++) add(i+16,i,r[i]-x); add(0,24,x); add(24,0,-x); for(i=8;i<=24;i++){ add(i-8,i,r[i]); } for(i=1;i<=24;i++){ add(i-1,i,0); add(i,i-1,-num[i]); } } bool spfa(int x){ build(x); memset(dis,-0x3f,sizeof dis); memset(st,0,sizeof st); memset(cnt,0,sizeof cnt); queue<int> q; q.push(0); dis[0]=0; while(q.size()){ int t=q.front(); q.pop(); int i; st[t]=0; for(i=h[t];i!=-1;i=ne[i]){ int j=e[i]; if(dis[j]<dis[t]+w[i]){ dis[j]=dis[t]+w[i]; cnt[j]=cnt[j]+1; if(cnt[j]>=25) return false; if(!st[j]){ q.push(j); st[j]=1; } } } } return true; } int main(){ int t; cin>>t; while(t--){ int n; int i; memset(num,0,sizeof num); for(i=1;i<=24;i++){ cin>>r[i]; } cin>>n; for(i=1;i<=n;i++){ int x; cin>>x; num[x+1]++; } int flag=0; for(i=1;i<=1000;i++){ if(spfa(i)){ flag=1; break; } } if(i==1001) cout<<"No Solution"<<endl; else{ cout<<i<<endl; } } }