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

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

1
Sorry
2

#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,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,sizeof sx); memset(sy,sizeof sy); memset(a,sizeof a); memset(b,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 */