#P5353. 猜测

    ID: 4366 传统题 1000ms 256MiB 尝试: 15 已通过: 7 难度: 6 上传者: 标签>CF2000提高二分图建模指定流量最小费用流Bellman–Ford残量网络离散化

猜测

题目描述

一个 105×10510^5\times10^5 的棋盘上有 nn 个不同的格子被选中。将这些格子的行坐标和列坐标分别抄成两个长度为 nn 的序列,再各自打乱,原先的行列对应关系丢失。

一次合法猜测需把这两个坐标序列的元素一一配对,形成 nn 个彼此不同的格子。给定真实选中的格子,求在所有合法猜测中,猜测格子与真实格子的最小重合个数。

输入格式

第一行一个整数 nn。接下来 nn 行,每行两个整数 xi,yix_i,y_i,表示一个真实格子的行坐标和列坐标。

输出格式

输出一个整数,表示最小重合个数。

样例 1

2
1 1
2 2
0

可以猜测 (1,2),(2,1)(1,2),(2,1),两个格子均与真实格子不同。

样例 2

3
1 1
1 2
2 1
3

用 (1,1),(1,1),(2,2)(1,1),(1,1),(2,2) 配对会重复使用同一格子,属于非法猜测。

数据范围

  • 30%30\% 的数据满足 n≤8n\le8。
  • 另外 5%5\% 的数据中,所有行坐标互异,且所有列坐标互异。
  • 另外 15%15\% 的数据中,所有行坐标互异,或所有列坐标互异。
  • 所有数据满足 1≤n≤501\le n\le50,1≤xi,yi≤1051\le x_i,y_i\le10^5。

原 PDF 题面