题目链接：点击打开链接

2
0 1 1
1 1 2
3
0 1 1
0 2 2
1 1 2
3
1 1 1
1 2 2
1 1 2

1
Sorry
2

题意：

给定n个二维坐标上的点

下面n行：

Fi, xi, yi

若Fi=0表示这个点不能删除

若Fi=1表示这个点必须删除

每次操作可以选任意一行或一列（注意这行（列）里不能有不可删除的点），把这行上的所有可删除点删除

问：最小操作次数。

思路：

若都是必须删除的点，那么就是经典的最小点覆盖

这题中：可删除点有3种

1、x y坐标都存在不能删除的点，这时候就输出 Sorry

2、x或y存在不能删除的点，那么我们强行选这个点的行（或列），并把该行所有点删掉。

3、经过上面2种操作就只有x y都不存在 不能删除点，这种点就是最小点覆盖。

补充最小点覆盖知识：

对于二部图，图中有一些边。

要选择最少的点使得所有边都被覆盖（当这条边的任意一个端点被选择或者两个端点同时被选择，则称这条边被覆盖了）

yy得证：

最小顶点覆盖数 = 最大匹配数

而那些没有被选择的点统称最大团

所以最大团 = X集点数+Y集点数 - 最小点覆盖数

即 ：最大团 = X集点数+Y集点数 - 最大匹配数

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<set>
#include<queue>
#include<algorithm>
#include<math.h>
using namespace std;
#define N 1005
int lef[N], pn;//lef[v]表示Y集的点v 当前连接的点 , pn为x点集的点数
bool T[N];     //T[u] 表示Y集 u 是否已连接X集
vector<int>G[N]; //匹配边  G[X集].push_back(Y集)  注意G 初始化

int sx[N], sy[N];
bool match(int x){ // x和Y集 匹配 返回x点是否匹配成功
	for(int i=0; i<G[x].size(); i++)
	{
		int v = G[x][i];
		if(!T[v])
		{
			T[v] = true;
			if(lef[v] == -1 || match( lef[v] ))   //match(lef[v]) : 原本连接v的X集点 lef[v] 能不能和别人连，如果能 则v这个点就空出来和x连
			{
				lef[v] = x;
				return true;
			}
		}
	}
	return false;
}

int solve(){
    memset(lef, -1, sizeof(lef));
    int ans = 0;
    for(int i = 1; i <= pn; i++)
    {
        memset(T, 0, sizeof T);
        if(match(i)){
       // 	printf("ok:%d\n", i);
			ans++;
		}
    }
    return ans;
}
vector<int>gx, gy;
int f[N], x[N], y[N], a[N], b[N];
int n, papa;
bool input(){
	gx.clear(); gy.clear();

	for(int i = 1; i <= n; i++)
	{
		scanf("%d %d %d", &f[i], &x[i], &y[i]);
		gx.push_back(x[i]);
		gy.push_back(y[i]);
	}
	sort(gx.begin(), gx.end());
	sort(gy.begin(), gy.end());
	gx.erase(unique(gx.begin(), gx.end()), gx.end());
	gy.erase(unique(gy.begin(), gy.end()), gy.end());
	memset(sx, 0, sizeof sx);
	memset(sy, 0, sizeof sy);
	memset(a, 0, sizeof a);
	memset(b, 0, sizeof b);
	for(int i = 1; i <= n; i++)
	{
		x[i] = lower_bound(gx.begin(), gx.end(), x[i]) - gx.begin()+1;
		y[i] = lower_bound(gy.begin(), gy.end(), y[i]) - gy.begin()+1;
		if(f[i] == 0)
		{
			sx[x[i]] = sy[y[i]] = 1;
		}
	}
	for(int i = 1; i <= (int)gx.size(); i++)G[i].clear();
	papa = 0;
	for(int i = 1; i <= n; i++)
	{
		if(f[i] == 0)continue;
		if(sx[x[i]] && sy[y[i]])
			return false;
		if(sx[x[i]])
		{
			if(b[y[i]])continue;
			b[y[i]] = 1; papa++;
		}
		else if(sy[y[i]])
		{
			if(a[x[i]])continue;
			a[x[i]] = 1; papa++;
		}
	}
	for(int i = 1; i <= n; i++)
	{
		if(f[i] == 0)continue;
		if(a[x[i]] || b[y[i]])continue;
		G[x[i]].push_back(y[i]);
	}
	return true;
}
int main() {
	while(~scanf("%d", &n)){
 	if(false == input())
		{
			puts("Sorry"); continue;
		}
		pn = (int)gx.size();
		int ans = solve();
//		printf("(匹配边数%d)\n", ans);
		ans = papa+ans;
	//	printf("pn:%d\nGX:", pn);		for(int i = 0; i < gx.size(); i++)printf("%d ", gx[i]);cout<<"\n"<<"GY:";		for(int i = 0; i < gy.size(); i++)printf("%d ", gy[i]);puts("");
			printf("%d\n", ans);
	}
	return 0;
}/*
4
1 1 1
1 2 2
1 1 2
0 2 1

6
1 1 1
1 2 2
1 1 2
0 2 1
0 2 3
0 1 0

3
1 1 2
1 1 3
1 1 4

5
1 0 0
1 1 0
0 2 0
1 1 1
0 2 1

25
0 1 1
0 1 2
0 1 3
0 2 1
0 2 2

0 2 3
0 3 1
0 3 2
0 3 3
1 0 0

1 1 0
1 2 0
1 3 0
1 4 0
1 0 2

1 4 2
1 0 1
1 4 1
1 0 3
1 4 3

1 0 4
1 4 4
1 1 4
1 2 4
1 3 4

25
1 1 1
1 1 2
1 1 3
1 2 1
0 2 2

1 2 3
1 3 1
1 3 2
1 3 3
1 0 0

1 1 0
1 2 0
1 3 0
1 4 0
1 0 2

1 4 2
1 0 1
1 4 1
1 0 3
1 4 3

1 0 4
1 4 4
1 1 4
1 2 4
1 3 4

3
1 1 1
1 1 1
1 1 2

*/

HNU 2014 Warm Up 15 E Easy Delete 最小点覆盖=最大匹配数