HNU 13103 Easy Delete 最小點(diǎn)覆蓋=最大匹配數(shù)
來源：程序員人生 發(fā)布時(shí)間：2014-12-19 08:24:40 閱讀次數(shù)：2690次
題目鏈接：點(diǎn)擊打開鏈接
|
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個(gè)2維坐標(biāo)上的點(diǎn)
下面n行：
Fi, xi, yi
若Fi=0表示這個(gè)點(diǎn)不能刪除
若Fi=1表示這個(gè)點(diǎn)必須刪除
每次操作可以選任意1行或1列（注意這行（列）里不能有不可刪除的點(diǎn)），把這行上的所有可刪除點(diǎn)刪除
問：最小操作次數(shù)。
思路：
若都是必須刪除的點(diǎn)，那末就是經(jīng)典的最小點(diǎn)覆蓋
這題中：可刪除點(diǎn)有3種
1、x y坐標(biāo)都存在不能刪除的點(diǎn)，這時(shí)候候就輸出 Sorry
2、x或y存在不能刪除的點(diǎn)，那末我們強(qiáng)行選這個(gè)點(diǎn)的行（或列），并把該行所有點(diǎn)刪掉。
3、經(jīng)過上面2種操作就只有x y都不存在 不能刪除點(diǎn)，這類點(diǎn)就是最小點(diǎn)覆蓋。
補(bǔ)充最小點(diǎn)覆蓋知識(shí)：
對(duì)2部圖，圖中有1些邊。
要選擇最少的點(diǎn)使得所有邊都被覆蓋（當(dāng)這條邊的任意1個(gè)端點(diǎn)被選擇或兩個(gè)端點(diǎn)同時(shí)被選擇，則稱這條邊被覆蓋了）
yy得證：
最小頂點(diǎn)覆蓋數(shù) = 最大匹配數(shù)
而那些沒有被選擇的點(diǎn)統(tǒng)稱最大團(tuán)
所以最大團(tuán) = X集點(diǎn)數(shù)+Y集點(diǎn)數(shù) - 最小點(diǎn)覆蓋數(shù)
即 ：最大團(tuán) = X集點(diǎn)數(shù)+Y集點(diǎn)數(shù) - 最大匹配數(shù)
#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集的點(diǎn)v 當(dāng)前連接的點(diǎn) , pn為x點(diǎn)集的點(diǎn)數(shù)
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點(diǎn)是不是匹配成功
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集點(diǎn) lef[v] 能不能和他人連，如果能 則v這個(gè)點(diǎn)就空出來和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("(匹配邊數(shù)%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
*/
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)
