题解：CF2059C Customer Service

minazuki_hotaru · 2026-04-23 22:03:00 · 题解

二分图匹配

力大砖飞，时间复杂度并非最优。

假如当前时刻是 j，我们不难发现，我们想要在这个时刻让他接上答案的话，他必须是 n - j + 1，这里问题转化成了一个经典的二分图最大匹配问题。

下面解释下为什么要这么做：

我们发现 a_{i,j} \ge 1，如果我们要从某个队列里凑出目标值 v，由于后缀里的每个数都 \ge 1，这个后缀最多只能包含 j 个数。这意味着：

• 要凑出值 0，我们需要一个清除后后缀长度为 0 的队列。
• 要凑出值 1，我们需要一个清除后后缀长度为 1 的队列。
• 要凑出值 v，我们需要一个清除后后缀长度为 v 的队列。

我们发现：为了得到 v，我们只能占用起点 j = n - v + 1。

下面就是建图：

用 0-n 表示值（因为答案不会超过 n），用 n+1 - 2n 表示队列，如果 i 号队列中后缀 j = n - v + 1，我们就把 v 与 i+n 点连一条边。

最后跑一下匈牙利算法就能过了，下面是 AC 代码。

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0),cout.tie(0)
#define endl '\n'
#define rep(i,a,b) for(int i = a ; i <= b ; i++)
#define per(i,a,b) for(int i = a ; i >= b ; i--)
#define int long long
using namespace std;
const int MAXN = 1e3 + 10;
vector<int> graph[MAXN];
int vis[MAXN],match[MAXN];
bool dfs(int u){
    for(auto& v : graph[u]){
        if(vis[v])continue;
        vis[v] = 1;
        if(match[v] == -1 || dfs(match[v])){
            match[v] = u;
            return 1;
        }
    }
    return 0;
}
void solve() {
    int n;
    cin >> n;
    vector<vector<int>> arr(n+1,vector<int>(n+1));
    rep(i,0,n * 2) {
        graph[i].clear();
    }
    rep(i,1,n) {
        rep(j,1,n)cin >> arr[i][j];
    }
    vector<vector<int>> suf(n+1,vector<int>(n + 2));
    memset(match,-1,sizeof(match));
    rep(i,1,n)per(j,n,1)suf[i][j] = suf[i][j + 1] + arr[i][j];
    rep(i,1,n) {
        rep(j,1,n+1) {
            if (suf[i][j] > n)continue;
            if (suf[i][j] != n - j + 1)continue;
            graph[suf[i][j]].push_back(i + n);
            graph[i + n].push_back(suf[i][j]);
        }
    }
    int ans = 1;
    rep(i,0,n) {
        memset(vis, 0, sizeof(vis));
        if (dfs(i)) {
            ans = i + 1;
        }
        else {
            break;
        }
    }
    cout << ans << endl;
}
signed main() {
    IOS;
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}