题目链接：C.Jiaxun!

看到最小值最大很容易想到二分答案然后贪心 $\text{check}$ ，但是贪心可能相对来说容易写错，赛时讨论了好几种贪心策略，最后到一个半小时的时候才过了这题，至少还是一发过了没有因为额外罚时雪上加霜。

所以使用一个一定正确的 $\text{check}$ 尤为重要，故考虑网络流。

我们设二分出来的最小值为 $x$ 。 显然我们需要给三个人分配题数让他们的题数均大于 $x$ ，而每个人额外多分配的题数不用考虑，因为只有最小值才会影响答案，考虑每个人向汇点连接一条容量为 $x$ 的边，代表这个人至少需要 $x$ 道题，然后从源点向每一类题连边，容量为该类题目的数量，代表一共对于第 $i$ 类有 $cap_i$ 道题目可以提供，最后根据题目中对题目类型描述，对应题目类型向可以做这类题的人连边，容量为 $+\infty $ ，代表这个题目可以为对应的人提供做题数，然后跑最大流，判断 $maxflow$ 是否等于 $3*x$ ，如果等于则代表当前二分的 $x$ 可以被满足，否则无法满足。时间复杂度为 $O(T \log \frac{S}{3} V \sqrt E )$ ，在实现较好的情况下可以通过此题。

代码↓：

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

using i64 = long long;
#define endl '\n'

const int MAXN = 1e2 + 10;

struct Edge
{
    int to, next;
    int val;
} edge[MAXN << 1];
int head[MAXN], tot = 1;

void addEdge(int u, int v, int val)
{
    edge[++tot] = {v, head[u], val};
    head[u] = tot;

    edge[++tot] = {u, head[v], 0};
    head[v] = tot;
}

int dep[MAXN], now[MAXN];

bool bfs(int s, int t)
{
    for (int i = s; i <= t; i++)
        dep[i] = 0;
    queue<int> que;
    dep[s] = 1;
    now[s] = head[s];
    que.push(s);
    while (!que.empty())
    {
        int u = que.front();
        que.pop();
        for (int i = head[u]; i; i = edge[i].next)
        {
            int v = edge[i].to;
            int w = edge[i].val;
            if (!dep[v] && w)
            {
                dep[v] = dep[u] + 1;
                now[v] = head[v];
                que.push(v);
                if (v == t)
                    return true;
            }
        }
    }
    return false;
}

int dfs(int u, int t, int sum)
{
    if (u == t)
        return sum;
    int res = 0;
    for (int &i = now[u]; i && sum; i = edge[i].next)
    {
        int v = edge[i].to;
        int w = edge[i].val;
        if (dep[v] == dep[u] + 1 && w)
        {
            int k = dfs(v, t, min(sum, w));
            if (!k)
                dep[v] = 0;
            edge[i].val -= k;
            edge[i ^ 1].val += k;
            res += k;
            sum -= k;
        }
    }
    return res;
}

signed main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int Case;
    cin >> Case;
    while (Case--)
    {
        int S;
        cin >> S;
        int n = 7;
        vector<int> val(n + 1);
        for (int i = 1; i <= n; i++)
            cin >> val[i];

        auto check = [&](int x) -> bool
        {
            const int INF = numeric_limits<int>::max();
            int s = 0, t = n + 3 + 1;
            for (int i = s; i <= t; i++)
                head[i] = 0;
            tot = 1;
            for (int i = 1; i <= 3; i++)
                addEdge(i + n, t, x);
            for (int i = 1; i <= n; i++)
                addEdge(s, i, val[i]);
            addEdge(1, n + 1, INF);
            addEdge(2, n + 2, INF);
            addEdge(3, n + 1, INF);
            addEdge(3, n + 2, INF);
            addEdge(4, n + 3, INF);
            addEdge(5, n + 1, INF);
            addEdge(5, n + 3, INF);
            addEdge(6, n + 2, INF);
            addEdge(6, n + 3, INF);
            addEdge(7, n + 1, INF);
            addEdge(7, n + 2, INF);
            addEdge(7, n + 3, INF);
            int maxflow = 0;
            while (bfs(s, t))
                maxflow += dfs(s, t, INF);
            return maxflow == 3 * x;
        };

        int l = 0, r = S / 3;
        while (l < r)
        {
            int mid = l + r + 1 >> 1;
            if (check(mid))
                l = mid;
            else
                r = mid - 1;
        }
        cout << l << endl;
    }

    return 0;
}