TMD.cpp

TMD.cpp

#include <bits/stdc++.h>

using namespace std;

const int MAX_V = 22222;
int V;
vector<int> g[MAX_V];
int match[MAX_V];
bool used[MAX_V];

void add_edge(int u, int v) {
    g[u].push_back(v);
    g[v].push_back(u);
}

// 回傳有無找到從 v 出發的增廣路徑
//（首尾都為未匹配點的交錯路徑）
// [待確認] 每次遞迴都找一個末匹配點 v 及匹配點 u
bool dfs(int v) {
    used[v] = true;
    for (size_t i = 0; i < g[v].size(); i++) {
        int u = g[v][i], w = match[u];
        // 尚未配對或可從 w 找到增廣路徑（即路徑繼續增長）
        if (w < 0 || (!used[w] && dfs(w))) {
            // 交錯配對
            match[v] = u;
            match[u] = v;
            return true;
        }
    }
    return false;
}

int bipartite_matching() { // 匈牙利演算法
    int res = 0;
    memset(match, -1, sizeof(match));
    for (int v = 0; v < V; v++) {
        if (match[v] == -1) {
            memset(used, false, sizeof(used));
            if (dfs(v)) {
                res++;
            }
        }
    }
    return res;
}

struct Data {
    int r, s, t;
};

typedef pair<int, int> ii;

void solve(int n)
{
    set<int> left;
    set<ii> right;
    Data inp[n];
    for(int i = 0; i < n; i++) {
        int r, s, t; // t / s
        scanf("%d %d %d", &r, &s, &t);
        int gg = __gcd(s, t);
        inp[i] = Data{r, s / gg, t / gg};

        left.insert(r);
        right.insert(ii(s / gg, t / gg));
    }

    V = left.size() + right.size();
    for(int i = 0; i < MAX_V; i++)
        g[i].clear();

    map<int, int> leftleft;
    int idx = 0;
    for(auto i : left) {
        leftleft[i] = idx;
        idx++;
    }
    map<ii, int> rightright;
    idx = 0;
    for(auto i : right) {
        rightright[i] = idx;
        idx++;
    }

    for(int i = 0; i < n; i++) {
        int l = leftleft[inp[i].r];
        int r = rightright[ii(inp[i].s, inp[i].t)];

        //printf("%d %d\n", l, r);

        add_edge(l, left.size() + r);
    }

    printf("%d\n", bipartite_matching());
}

int main()
{
    //freopen("test.in", "r", stdin);
    int ncase;
    scanf("%d", &ncase);

    while(ncase--) {
        int n;
        scanf("%d", &n);

        solve(n);
    }

    return 0;
}