HNU 13103 Easy Delete 最小点覆盖=最大匹配数
来源：程序员人生 发布时间：2014-12-19 08:24:40 阅读次数：2488次
题目链接：点击打开链接
|
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
*/
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
