Cod sursă (job #179516)

#include <bits/stdc++.h>
using namespace std;
const int Nmax=2048+1;
struct Canibal
{
    int X,Y,Z,T;
    bool operator < (const Canibal& A) const {return (X<A.X&&Y<A.Y&&Z<A.Z&&T<A.T);}
    bool operator==(const Canibal& A) const {return (X==A.X&&Y==A.Y&&Z==A.Z&&T==A.T);}
};
Canibal C[Nmax];
vector<int>G[2*Nmax];
bool used[2*Nmax];
int L[2*Nmax],R[2*Nmax],N,i,j;
bool validEdge(int x,int y)
{
    if(C[y]==C[x]) return x<y;
    return C[y]<C[x];
}
bool pairUp(int nod)
{
    if(used[nod]) return 0;
    used[nod]=1;
    for(auto son: G[nod]) if(!R[son]) {L[nod]=son;R[son]=nod;return 1;}
    for(auto son: G[nod]) if(pairUp(R[son])) {L[nod]=son;R[son]=nod;return 1;}
    return 0;
}
int matching()
{
    int nr_c=0,ok;
    do
    {
        ok=0;
        memset(used,0,sizeof(used));
        for(i=1;i<=2*N;++i) if(!L[i]) ok |= pairUp(i);
    }while(ok);
    for(i=1;i<=2*N;++i) nr_c+=(L[i]>0);
    return nr_c;
}
int main()
{
    ifstream f("canibali.in");
    ofstream g("canibali.out");
    f>>N;
    for(i=1;i<=N;++i) f>>C[i].X>>C[i].Y>>C[i].Z>>C[i].T;
    for(i=1;i<=N;++i)
        for(j=1;j<=N;++j)
            if(validEdge(i,j)) G[i].push_back(j),G[i+N].push_back(j);
    g<<N-matching();
    return 0;
}