Cod sursă (job #308984)

#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream in("canibali.in");
ofstream out("canibali.out");

const int NMAX = 2048;

int n;
int a[1 + NMAX][5];
int dist[1 + 3 * NMAX];
int match[1 + 3 * NMAX];
bool vis[1 + 3 * NMAX];

vector < int > g[1 + 3 * NMAX];

void addedge(int x, int y){
  g[x].push_back(y);
  g[y].push_back(x);
}

void bfs(){
  queue < int > q;
  fill(dist + 1, dist + n * 3 + 1, -1);

  for(int i = 1; i <= n; i++){
    if(match[i] <= 0){
      q.push(i);
      dist[i] = 0;
    }
  }

  while(!q.empty()){
    int u1 = q.front();
    q.pop();
    for(int i = 0; i < g[u1].size(); i++){
      int v1 = g[u1][i];
      int u2 = match[v1];

      if(0 < u2 && dist[u2] < 0){
        dist[u2] = dist[u1] + 1;
        q.push(u2);
      }
    }
  }
}

bool dfs(int u1){
  vis[u1] = true;
  for(int i = 0; i < g[u1].size(); i++){
    int v1 = g[u1][i];
    int u2 = match[v1];

    if(u2 <= 0){
      match[u1] = v1;
      match[v1] = u1;
      return true;
    } else if(vis[u2] == false && dist[u2] == dist[u1] + 1){
      if(dfs(u2) == true){
        match[u1] = v1;
        match[v1] = u1;
        return true;
      }
    }
  }
  return false;
}

int maxmatching(){
  int answer = 0;
  int add = 1;

  while(0 < add){
    fill(vis + 1, vis + n * 3 + 1, false);
    add = 0;
    bfs();

    for(int i = 1; i <= n; i++){
      if(match[i] <= 0){
        if(dfs(i) == true)
          add++;
      }
    }
    answer += add;
  }
  return answer;
}

int cmp(int x, int y){
  int s = 0;
  for(int i = 1; i <= 4; i++){
    if(a[y][i] <= a[x][i]){
      if(s >= 0)
        s = 1;
      else
        s = -1;
    } else if(a[x][i] < a[y][i]){
      s = -1;
    }
  }

  return s;
}

int main()
{
  in >> n;
  for(int i = 1; i <= n; i++){
    for(int j = 1; j <= 4; j++){
      in >> a[i][j];
    }
  }

  for(int i = 1; i <= n; i++){
    for(int j = 1; j <= n; j++){
      if(i != j){
        int x = cmp(i, j);
        if(x == 1){
          addedge(i, j + 2 * n);
          addedge(i + n, j + 2 * n);
          //cout << i << ' ' << j + n << '\n';
        }
      }
    }
  }

  out << max(1, n - maxmatching()) << '\n';

  in.close();
  out.close();
  return 0;
}