在线建图SPFA

#include <bits/stdc++.h>
using namespace std;

const int N=30;
const int M=80; // 统计出差分系统方程组的个数不超过80个
const int K=1005;
int a[N], r[N], dist[N], cnt[N], head[N];
bool vis[N];
int n, T, E;

struct Edge{int v, w, ne;}e[M];
inline void add(int a, int b, int c){
    e[E].v=b;
    e[E].w=c;
    e[E].ne=head[a];
    head[a]=E++;
}

// 在线建图
void G(int R){
    memset(head, -1, sizeof head);
    E=0;
    add(0, 24, R); add(24, 0, -R); // S24作为常量单独处理
    for(int i=1; i<=7; ++i) add(i+16, i, r[i]-R);
    for(int i=8; i<=24; ++i) add(i-8, i, r[i]);
    for(int i=1; i<=24; ++i) {add(i-1, i, 0); add(i, i-1,-a[i]);}   
}

inline void init(){
    memset(dist, 0xcf, sizeof dist);
    memset(cnt, 0x00, sizeof cnt);
    memset(vis, 0x00, sizeof vis);
}

bool spfa(int R){
    G(R);
    init();
    queue<int> q;
    q.push(0); // 0点为超级源点
    dist[0]=0;
    vis[0]=true;
    while(!q.empty()){
        int node=q.front(); q.pop(); vis[node]=false;
        for(int i=head[node]; ~i; i=e[i].ne){
            int v=e[i].v;
            if(dist[v]<dist[node]+e[i].w){
                dist[v]=dist[node]+e[i].w;
                cnt[v]=cnt[node]+1;
                if(cnt[v]>=25) return true;
                if(!vis[v]){q.push(v); vis[v]=true;}
            }
        }
    }
    return false;
}

int main(){
    cin>>T;
    while(T--){
        memset(a, 0x00, sizeof a);
        for(int i=1; i<=24; ++i) cin>>r[i];
        cin>>n;
        int t;
        for(int i=0; i<n; ++i){
            cin>>t;
            a[t+1]++; // 0-23工作转为1-24工作
        }
        bool flag=false;
        // 线性扫描最小值(可以满足要求的最小的R)
        for(int i=0; i<K; ++i){
            if(!spfa(i)) {cout<<i<<endl; flag=true; break;}
        }
        if(!flag) cout<<"No Solution"<<endl;
    }
    return 0;
}