# HUNNU11564 Easy Delete（二分图匹配/最小点覆盖+离散化）

## Easy Delete

• Time Limit: 1500ms, Special Time Limit:2500ms,
• Memory Limit:65536KB
• Total submit users: 7
• Accepted users: 4

### Problem description

huicpc0215 has downloaded a lots of files in his desktop. Since there are too many files in the desktop, he wants to delete some files in the desktop. But some files can’t be deleted.

$$Figure 1 Messy Desktop$$
Each time he can choose one row or column to delete. But attention he can’t choose one row or column that has a file which can’t be deleted. Given the position of all files, please get the minimum steps for huicpc0215 to delete all files that he wants to delete.

### Input

There are multiple test cases. Each test case containing:
The first line contains one integer: N (1 <= N <= 1000) , N lines follows. Each line contains three integers: F (0 <= F <= 1), X ($-1e^9 <= V <= 1e^9$), Y ($-1e^9 <= V <= 1e^9$). F=0 means this file can’t be delete. F =1 means this file must be deleted. And X and Y are the position of the file in the desktop.

### Output

If huicpc0215 can achieve his goal, print minimum steps to achieve his goal, otherwise print “Sorry” in one line.

### Sample Input

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

### Sample Output

1
Sorry
2

2014哈尔滨理工大学秋季训练赛

### 链接

http://acm.hunnu.edu.cn/online/?action=problem&type=show&id=11564

### 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int maxn = 1010;

vector <int> gx, gy, G[maxn];
int f[maxn], x[maxn], y[maxn], a[maxn], b[maxn], sx[maxn], sy[maxn], linker[maxn], used[maxn];
int n, tot, uN;

void init()
{
tot = 0;
gx.clear(), gy.clear();
memset(sx, 0, sizeof(sx)); // 标记所在行是否能够删除
memset(sy, 0, sizeof(sy)); // 标记所在列是否能够删除
memset(a, 0, sizeof(a)); // 标记需要单独删除的行
memset(b, 0, sizeof(b)); // 标记需要单独删除的列
for (int i = 0; i <= n; ++i)
G[i].clear();
}

bool dfs(int u) // 递归寻找匹配
{
for (int i = 0; i < G[u].size(); ++i)
{
int v = G[u][i];
if (!used[v])
{
used[v] = true;
{
return true;
}
}
}
return false;
}

int solve() // 二分图匹配
{
int res = 0;
uN = gx.size();
for (int u = 1; u <= uN; ++u)
{
memset(used, 0, sizeof(used));
if (dfs(u))
++res;
}
return res;
}

int main()
{
while (scanf("%d", &n) != EOF)
{
init();
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());
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;
}
bool flag = true;
for (int i = 1; i <= n; ++i)
{
if (f[i] == 0)
continue;
if (sx[x[i]] && sy[y[i]]) // 行和列都不可被删除，出现矛盾
{
flag = false;
break;
}
if (sx[x[i]]) // 行不可以删除
{
if (b[y[i]])
continue;
b[y[i]] = 1; // 删除列
tot++;
}
if (sy[y[i]]) // 列不可以删除
{
if (a[x[i]])
continue;
a[x[i]] = 1; // 删除行
tot++;
}
}
if (!flag)
{
printf("Sorry\n");
continue;
}
for (int i = 1; i <= n; ++i)
{
if (f[i] == 0 || a[x[i]] || b[y[i]])
continue;
G[x[i]].push_back(y[i]); // 行和列都可以被删除，连边
}
int ans = solve() + tot;
printf("%d\n", ans);
}
return 0;
}

The end.
2018-08-19 星期日