Cod sursă (job #183097)

#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;

}