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

题意:

给定n个2维坐标上的点

下面n行:

Fi, xi, yi

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

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

每次操作可以选任意1行或1列(注意这行(列)里不能有不可删除的点),把这行上的所有可删除点删除

问:最小操作次数。

思路:

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

这题中:可删除点有3种

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

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

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

补充最小点覆盖知识:

对2部图,图中有1些边。

要选择最少的点使得所有边都被覆盖(当这条边的任意1个端点被选择或两个端点同时被选择,则称这条边被覆盖了)

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] == ⑴ || 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

*/

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

波比源码 » HNU 13103 Easy Delete 最小点覆盖=最大匹配数

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡