Участник:Morgachev/ADABLOOM

Материал из DISCOPAL
Перейти к: навигация, поиск

https://www.spoj.com/problems/ADABLOOM/

C++14 (clang8.0)

#include<vector>
#include<sstream>
#include<iostream>
#include<algorithm>
#include<queue>
 
 
using namespace std;
 
#define int long long
const int N = 5005;
 
 
struct HopcroftKarp {
    static const int inf = 1e9;
 
    int n;
    vector<int> matchL, matchR, dist;
    vector<vector<int> > g;
 
    HopcroftKarp(int n) : n(n), matchL(n + 1), matchR(n + 1), dist(n + 1), g(n + 1) {}
 
    void addEdge(int u, int v) {
        g[u].push_back(v);
    }
 
    bool bfs() {
        queue<int> q;
        for (int u = 1; u <= n; u++) {
            if (!matchL[u]) {
                dist[u] = 0;
                q.push(u);
            } else
                dist[u] = inf;
        }
        dist[0] = inf;
 
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (auto v:g[u]) {
                if (dist[matchR[v]] == inf) {
                    dist[matchR[v]] = dist[u] + 1;
                    q.push(matchR[v]);
                }
            }
        }
 
        return (dist[0] != inf);
    }
 
    bool dfs(int u) {
        if (!u) {
            return true;
        }
        for (auto v:g[u]) {
            if (dist[matchR[v]] == dist[u] + 1 && dfs(matchR[v])) {
                matchL[u] = v;
                matchR[v] = u;
                return true;
            }
        }
        dist[u] = inf;
        return false;
    }
 
    int max_matching() {
        int matching = 0;
        while (bfs()) {
            for (int u = 1; u <= n; u++) {
                if (!matchL[u]) {
                    if (dfs(u)) {
                        matching++;
                    }
                }
            }
        }
        return matching;
    }
};
 
 
int32_t main() {
    int n;
    int a[N];
    int t;
    cin >> t;
    while (t--) {
        cin >> n;
        for (int i = 1; i <= n; i++)
            cin >> a[i];
 
        HopcroftKarp flow(n + 1);
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                int l = a[i], m = a[i] ^a[j], r = a[j];
                if (l < m && m < r && l < r)
                    flow.addEdge(i, j);
                if (l > m && m > r && l > r)
                    flow.addEdge(i, j);
            }
        }
        cout << flow.max_matching() / 2 << "\n";
    }
    return 0;
}