# HNU 13103 Easy Delete 最小点覆盖=最大匹配数

 Easy Delete Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:65536KB Total submit users: 8, Accepted users: 4 Problem 13103 : No special judgement 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.   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 (⑴e9 <= V <= 1e9), Y (⑴e9 <= V <= 1e9). 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```

Fi, xi, yi

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

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

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

yy得证：

#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] == ⑴ || match( lef[v] )) //match(lef[v]) : 本来连接v的X集点 lef[v] 能不能和他人连，如果能 则v这个点就空出来和x连
{
lef[v] = x;
return true;
}
}
}
return false;
}

int solve(){
memset(lef, ⑴, sizeof(lef));
int ans = 0;
for(int i = 1; i <= pn; i++)
{
memset(T, 0, sizeof T);
if(match(i)){
// printf("ok:%d
", 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)
", ans);
ans = papa+ans;
// printf("pn:%d
GX:", pn); for(int i = 0; i < gx.size(); i++)printf("%d ", gx[i]);cout<<"
"<<"GY:"; for(int i = 0; i < gy.size(); i++)printf("%d ", gy[i]);puts("");
printf("%d
", 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

*/

1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！
2. 分享目的仅供大家学习和交流，您必须在下载后24小时内删除！
3. 不得使用于非法商业用途，不得违反国家法律。否则后果自负！
4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！
5. 如有链接无法下载、失效或广告，请联系管理员处理！
6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！
7. 本站源码并不保证全部能正常使用，仅供有技术基础的人学习研究，请谨慎下载
8. 如遇到加密压缩包，请使用WINRAR解压,如遇到无法解压的请联系管理员！