【2016湖南集训】猜测 guess

Description

有一块棋盘，棋盘的边长为 100000，行和列的编号为 1 到 100000。棋盘上有n个特殊格子，任意两个格子的位置都不相同。

现在小 K 要猜哪些格子是特殊格子。她知道所有格子的横坐标和纵坐标，但并不知道对应关系。换言之，她只有两个数组，一个存下了所有格子的横坐标，另一个存下了所有格子的纵坐标，而且两个数组都打乱了顺序。当然，小 K 猜的n个格子的位置也必须都不相同。

请求出一个最大的k，使得无论小 K 怎么猜，都能猜对至少k个格子的位置。

Input

输入数据第一行包含一个整数n。

接下来n行，每行描述一个特殊格子的位置。第#行含有两个整数x_i和y_i ，代表第i个格子的坐标。保证任意两个格子的坐标都不相同。

Output

输出一行，包含一个整数，代表最大的k。

Sample Input

1 1

1 2

2 1

Sample Output

HINT

此时只有一种合法的猜测。注意(1,1),(1,1),(2,2)不是一个合法的猜测。

对于 30%的数据，n ≤ 8。

另外有 5%的数据，所有横坐标和纵坐标均不相同。

另外有 15%的数据，所有横坐标或者纵坐标均不相同。

对于 100%的数据，n ≤ 50，1 ≤ x_i, y_i ≤ 100000。

Solution

最小费用最大流。

虽然题目中写的是求最大，但这题本质上求的是一个最小值：

在所有合法配对方案中，正确对数的最小值。

对于n<=8的数据，枚举排列就好。

对于一般的情况，我们可以使用费用流求解。建一个费用流模型：

– 对x和y中的每个不同元素分别建点；

– 从源向x中的元素连边，容量为元素出现次数，费用为0；

– 从y中的元素向汇连边，和上面类似；

– 对于每个x中的元素和每个y中的元素，连一条容量为1的边。如果这种搭配是正确的，费用为1，否则为0。

这个网络的最小费用最大流就是答案。

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <cstdio>
#include <queue>
using namespace std;
const int INF = 1009999999;
inline int getint() {
	int r = 0, k = 1; char c = getchar();
	for (; c < '0' || c > '9'; c = getchar()) if (c == '-') k = -1;
	for (; '0' <= c && c <= '9'; c = getchar()) r = r * 10 - '0' + c;
	return r * k;
}
int n, S, T;
namespace MinCost {
	const int maxn = 1005;
	const int maxnode = maxn*2+10;
	const int maxe = 80010;
	struct edge_type { int to, next, r, c; } edge[maxe];
	int h[maxnode], cnte = 1;
	void ins(const int u, const int v, const int f, const int c) {
		++cnte; edge[cnte].to = v; edge[cnte].next = h[u]; edge[cnte].r = f; edge[cnte].c = c; h[u] = cnte;
		++cnte; edge[cnte].to = u; edge[cnte].next = h[v]; edge[cnte].r = 0; edge[cnte].c = -c; h[v] = cnte;
	}
	queue<int> Q;
	int dis[maxnode], pre[maxnode], a[maxnode], ans = 0;
	bool vis[maxnode];
	inline bool SPFA(){
		while (!Q.empty()) Q.pop();
		for (int i = S; i <= T; ++i) vis[i] = false, dis[i] = INF;
		dis[S] = 0; Q.push(S); a[S] = INF; pre[S] = 0;
		int now;
		while (!Q.empty()) {
			now = Q.front(); Q.pop();
			vis[now] = false;
			for (int i = h[now]; i; i = edge[i].next) {
				if (edge[i].r && dis[edge[i].to] > dis[now] + edge[i].c) {
					dis[edge[i].to] = dis[now] + edge[i].c;
					pre[edge[i].to] = i;
					a[edge[i].to] = min(a[now], edge[i].r);
					if (!vis[edge[i].to]) {
						Q.push(edge[i].to);
						vis[edge[i].to] = true;
					}
				}
			}
		}
		if (dis[T] == INF) return false;
		ans += a[T] * dis[T];
		for (now = T; now != S; now = edge[pre[now]^1].to) {
			edge[pre[now]].r -= a[T];
			edge[pre[now]^1].r += a[T];
		}
		return true;
	}
	inline void MCMF() {
		ans = 0;
		while (SPFA());
	}
}
int A, B, X[233], Y[233], H[100005], tot, V[233][233];
int main() {
	n = getint();
	for (int i = 1; i <= n; ++i) {
		A = getint();
		if (!H[A]) H[A] = ++tot;
		A = H[A]; ++X[A];
		B = getint();
		if (!H[B]) H[B] = ++tot;
		B = H[B]; ++Y[B];
		V[A][B] = 1;
	}
	S = 0; T = 222;
	for (int i = 1; i <= 100; ++i) {
		if (X[i]) MinCost::ins(S, i, X[i], 0);
		if (Y[i]) MinCost::ins(i + 101, T, Y[i], 0);
	}
	for (int i = 1; i <= 100; ++i)
		if (X[i])
			for (int j = 1; j <= 100; ++j)
				if (Y[j])
					MinCost::ins(i, j + 101, 1, V[i][j]);
	MinCost::MCMF();
	printf("%d", MinCost::ans);
}