匈牙利演算法

開幾個array:
1. now -> 記錄該點目前被誰佔有
2. mark -> 記錄該點是否被嘗試過

範例

// Author : ysh
// 10/21/2022 Fri 16:06:37.82
// https://tioj.ck.tp.edu.tw/problems/1069
#include<bits/stdc++.h>
using namespace std;
struct box{
    int t,x,y;
    box(int t = 0,int x = 0,int y = 0):
        t(t), x(x), y(y) {};
    inline bool operator<(const box &a) const {
        return t > a.t;
    }
};
inline int dt(int a,int b,int c,int d) {
    return (abs(a - c) + abs(b - d));
}
int check(int n,vector<box>&f) {
    vector<vector<int>>v(n);
    vector<bool>mark;
    vector<int>now(n,-1);
    function<bool(int)> ck = [&] (int x) {
        for(int &i : v.at(x)) {
            if(mark.at(i)) continue;
            mark.at(i) = 1;
            if(now.at(i) != -1) {
                if(!ck(now.at(i))) {
                    continue;
                }
            }
            now.at(i) = x;
            return 1;
        }
        return 0;
    };
    for(int i = 0;i<n;i++) {
        for(int j = 0;j<n;j++) {
            if(i == j) continue;
            if(f[i].t < f[j].t && f.at(i).t + dt(f.at(i).x,f.at(i).y,f.at(j).x,f.at(j).y) <= f.at(j).t) {
                v.at(i).push_back(j);
            }
        }
    }
    int ans = 0;
    for(int i = 0;i<n;i++) {
        mark = vector<bool>(n);
        if(ck(i)) ans++;
    }
    return n - ans;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;cin>>n;
    while(n--) {
        int m;cin>>m;
        vector<box>f(m);
        for(auto &i : f) {
            cin>>i.t>>i.x>>i.y;
        }
        // sort(f.rbegin(),f.rend());
        cout<<check(m,f)<<"\n";
    }
    return 0;
}

做法

對於每一個點，記錄它能在時間內到達的其他點，存在v[]裡，接著對於每個點，我們可以發現，如果在時間內無法到達任何點，或是能到達的點都被佔領了，就需要多一位人員。

所以我們寫一個函數，嘗試為傳入的點匹配一個能到達的點，如果成功就回傳true，失敗則測試能否為已匹配的點找到其他可行的點，若都失敗，則回傳false。注意如果對於一個點，被多次呼叫（該次呼叫前就已經匹配過）時，就需要再為它匹配另一個點。

最後，我們只需要對於每個點呼叫一次函數，如果回傳false，代表無法匹配，所以將需要人數加一。