Cod sursă (job #143266)

//Cristian Lambru - Universitatea Bucuresti
//Solutie - Cuplaj maxim in graf bipartit - 100pt
#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
   
FILE *f = fopen("canibali.in","r");
FILE *g = fopen("canibali.out","w");
   
struct canibal
{
    int X, Y, Z, T;
} ;

#define MaxN 10100
  
int N,K,Sol;
canibal M[MaxN];
vector<int> A[MaxN];
int viz[MaxN],St[MaxN],Dr[MaxN];
   
void citire(void)
{
    fscanf(f,"%d",&N);
    for(int i=1;i<=N;i++)
        fscanf(f,"%d%d%d%d",&M[i].X,&M[i].Y,&M[i].Z,&M[i].T);
}
   
inline int existaMuchie(int a,int b)
{
    if(M[a].X < M[b].X || M[a].Y < M[b].Y || 
        M[a].Z < M[b].Z || M[a].T < M[b].T)
            return 0;
    if(a >= b && M[a].X == M[b].X && M[a].Y == M[b].Y 
        && M[a].Z == M[b].Z && M[a].T == M[b].T)
            return 0;

    return 1;
}
  
void creareGraf(void)
{
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++)
            if(existaMuchie(i,j))
            {
                A[i].push_back(j);
                A[N+i].push_back(j);
            }
}
   
inline int cupleaza(int nod)
{
    if(viz[nod])
        return 0;
    viz[nod] = 1;
    for(int i=0;i<A[nod].size();i++)
        if(!Dr[A[nod][i]])
        {
            St[nod] = A[nod][i];
            Dr[A[nod][i]] = nod;
 
            return 1;
        }
 
    for(int i=0;i<A[nod].size();i++)
        if(cupleaza(Dr[A[nod][i]]))
        {
            St[nod] = A[nod][i];
            Dr[A[nod][i]] = nod;
 
            return 1;
        }
 
    return 0;
}
  
void Rezolvare(void)
{
    int ok = 1;
    for(;ok;)
    {
        ok=0;
        for(int i=1;i<=N;i++)
            viz[i] = 0;
        for(int i=1; i<=N; i++)
            if(!St[i]) //nodul i nu a fost cuplat
                ok += cupleaza(i);
    }
 
    for(int i=1;i<=N;i++)
        if(!St[i])
            ++ Sol;
}
 
int main()
{
    citire();
    creareGraf();
    N <<= 1;
    Rezolvare();
   
    /*for(int i=1;i<=N;i++,printf("\n"))
    {
        printf("%d -> ",i);
        for(int j=0;j<A[i].size();j++)
            printf("%d ",A[i][j]);
    }*/
   
    fprintf(g,"%d\n",Sol-(N>>1));
}