雇佣收银员

AcWing-393-雇佣收银员

实现

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

const int N = 30, M = 100;
struct edge {
    int to, next, w;
};
edge e[M];
int idx, head[N];
int n;
int r[N], a[N];
int dis[N], cnt[N];
bool mark[N];

void add_edge (int u, int v, int w) {
    e[idx].w = w;
    e[idx].to = v;
    e[idx].next = head[u];
    head[u] = idx ++;
}
void initialize (int s24) {
    idx = 0;
    memset(head, -1, sizeof(head));
    for (int i = 1; i <= 24; ++ i) {
        add_edge(i - 1, i, 0);
        add_edge(i, i - 1, -a[i]);
    }
    for (int i = 8; i <= 24; ++ i)
        add_edge(i - 8, i, r[i]);
    for (int i = 1; i <= 7; ++ i)
        add_edge(i + 16, i, -s24 + r[i]);
    add_edge(0, 24, s24), add_edge(24, 0, -s24);
}
bool spfa (int s24) {
    initialize(s24);

    memset(mark, 0, sizeof(mark));
    memset(cnt, 0, sizeof(cnt));
    memset(dis, -0x3f, sizeof(dis));

    queue<int> q;
    dis[0] = 0;
    q.push(0);
    mark[0] = true;
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        mark[cur] = false;
        for (int i = head[cur]; i != -1; i = e[i].next) {
            int to = e[i].to, w = e[i].w;
            if (dis[cur] + w > dis[to]) {
                dis[to] = dis[cur] + w;
                cnt[to] = cnt[cur] + 1;
                if (cnt[to] >= N) return true;
                if (mark[to] == false) {
                    q.push(to);
                    mark[to] = true;
                }
            }
        }
    }
    return false;
}

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

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