HNU 13103 Easy Delete 最小點覆蓋=最大匹配數
來源：程序員人生 發布時間：2014-12-19 08:24:40 閱讀次數：2701次
題目鏈接：點擊打開鏈接
|
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
*/
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
