【題解】TIOJ 1069 E.魔法部的任務

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

int T, n, t[1005], x[1005], y[1005], m[1005], vis[1005], ans;
vector <int> v[1005], c;

bool f(int x){
    vis[x] = 1;
    c.push_back(x);
    for (auto &i:v[x]){
        if (!m[i]){
            m[i] = x;
            return 1;
        }
        if (vis[m[i]]) continue;
        if (f(m[i])){
            m[i] = x;
            return 1;
        }
    }
    return 0;
}

int main(){
    cin >> T;
    while (T--){
        cin >> n;
        for (int i = 1; i <= n; i++){
            cin >> t[i] >> x[i] >> y[i];
            v[i].clear();
            m[i] = 0;
        }
        for (int i = 1; i <= n; i++){
            for (int j = 1; j <= n; j++){
                if (t[i] < t[j] && abs(x[j]-x[i])+abs(y[j]-y[i]) <= (t[j]-t[i])){
                    v[i].push_back(j);
                }
            }
        }
        ans = n;
        for (int i = 1; i <= n; i++){
            if (f(i)) ans--;
            while (c.size()){
                vis[c.back()] = 0;
                c.pop_back();
            }
        }
        cout << ans << "\n";
    }
}