差分约束应用题

// 差分约束，此题难点在于如何找出这些关系
// 1-24是一个环，这里处理办法是把24时固定
// 当 i > 8 时，s[i] >= R[i] + s[i − 8]
// 当 i <= 7 时，s[i] >= s[16 + i] - s[24] + R[i]
// 当 1 <= i <= 24时，s[i] >= s[i − 1], s[i - 1] >= s[i] - num[i]

#include <iostream>
#include <cstring>

using namespace std;

const int N = 30, M = 100;

int nums[N], r[N];
int head[N], ver[M], edge[M], Next[M], tot;
int q[N], cnt[N], tt, hh;
int dist[N], n;
bool st[N];

void add(int u, int v, int w) {
    ver[++tot] = v, edge[tot] = w, Next[tot] = head[u], head[u] = tot;
}

void build(int C24) {
    memset(head, 0, sizeof head);
    tot = 0;
    for (int i = 1; i <= 24; i++) {
        add(i - 1, i, 0);
        add(i, i - 1, -nums[i]);
    }
    for (int i = 8; i <= 24; i++) add(i - 8, i, r[i]);
    for (int i = 1; i < 8; i++) add(i + 16, i, -C24 + r[i]);
    // 固定24，S24 >= C24 && C24 >= S24
    // 为了与0相连，所以 S24 >= C24 + S0, S0 >= S24 - C24;
    add(0, 24, C24), add(24, 0, -C24);
}

bool spfa(int C24) {

    build(C24);
    memset(dist, -0x3f, sizeof dist);
    memset(st, 0, sizeof st);
    memset(cnt, 0, sizeof cnt);

    hh = tt = 0;
    q[tt++] = 0;
    st[0] = true;
    dist[0] = 0;

    while (hh != tt) {
        int t = q[hh++];
        if (hh == N) hh = 0;
        st[t] = false;

        for (int i = head[t]; i; i = Next[i]) {
            int j = ver[i];

            if (dist[j] < dist[t] + edge[i]) {
                dist[j] = dist[t] + edge[i];
                cnt[j] = cnt[t] + 1;

                if (cnt[j] >= 25) return false;

                if (!st[j]) {
                    st[j] = true;
                    q[tt++] = j;
                    if (tt == N) tt = 0;
                }
            }
        }
    }
    return true;

}

int main() {
    int t;
    cin >> t;
    while (t--) {
        for (int i = 1; i <= 24; i++) cin >> r[i];
        cin >> n;
        memset(nums, 0, sizeof nums);
        for (int a, i = 0; i < n; i++) {
            cin >> a;
            nums[a + 1]++;
        }

        bool flag = false;
        for (int i = 0; i <= 1000; i++) {
            if (spfa(i)) {
                cout << i << endl;
                flag = true;
                break;
            }
        }
        if (!flag) puts("No Solution");
    }

    return 0;
}