Cod sursa(job #2586711)

Utilizator smoc_georgemarianSmoc George-Marian smoc_georgemarian Data 21 martie 2020 13:28:42
Problema Cuplaj maxim in graf bipartit Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.61 kb
#include <bits/stdc++.h>
#define NMAX 2050
using namespace std;
ifstream fin("canibali.in");
ofstream fout("canibali.out");
struct tip{int x,y,z,t;};
tip v[NMAX];
vector<int>g[2*NMAX];
int n;
bool ok=1;
bool uz[2*NMAX];
int st[2*NMAX];
int dr[2*NMAX];
void citire();
bool cup(int k);
bool compar1(int i, int j)
{
  tip a=v[i];
  tip b =v[j];
  return a.x>=b.x && a.y>=b.y && a.z>=b.z && a.t>=b.t;
}

bool compar(tip a, tip b)
{
  return a.x<b.x || a.x==b.x && a.y<b.y || a.x==b.x && a.y==b.y && a.z<b.z || a.x==b.x && a.y==b.y && a.z==b.z && a.t<b.t ;
}
int main()
{citire();
 while(ok)
    {
     int i;
     ok=0;
     memset(uz,0,sizeof(uz));
     for(i=1;i<=n;i++)
        if(!uz[i] && !st[i])
        {
         ok|=cup(i);
        }
    }
 int sol=0;
 for(int i=1;i<=n;i++)
     if(st[i] )
       sol++;
 fout<<n/2-sol;
return 0;
}
void citire()
{int i,j;
  fin>>n;
 for(i=1;i<=n;i++)
    fin>>v[i].x>>v[i].y>>v[i].z>>v[i].t;
sort(v+1,v+n+1,compar);
for(i=2;i<=n;i++)
    for(j=1;j<=i-1;j++)
        {
         if( compar1(i,j) )
            {
             g[i].push_back(j);
             g[i+n].push_back(j);
            }
        }
  n*=2;
}
bool cup(int k)
{int i;
  if(uz[k])
        return 0;
  uz[k]=1;
  for(i=0;i<g[k].size();i++)
    {
      int vec=g[k][i];
     if(!dr[vec])
        {
         st[k]=vec;
         dr[vec]=k;
         return 1;
        }
    }
  for(i=0;i<g[k].size();i++)
     {
      int vec=g[k][i];
      if(cup(dr[vec]) )
        {
         st[k]=vec;
         dr[vec]=k;
         return 1;
        }
     }
   return 0;
}