Idea:
Find the total number of matching and then check for every match(left,right) pair whether it is unique or not. To check this find total number of matching using the same algorithm just excluding a pair each time and compare the total number of founded match with the initial one. If it is not reduced than remove that pair.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 |
#include <iostream> #include <cstdio> #include <cstring> #include <vector> #include <map> using namespace std; struct Slide{ int Xmin,Xmax,Ymin,Ymax;}; struct POINT{int x,y;}; vector<int> gr[105]; Slide slide[105];/////// POINT pp[105]; bool visit[105]; int lef[105],rit[105]; int N; bool check(POINT a,Slide b) { if(a.x>=b.Xmin && a.x<=b.Xmax) { if(a.y>=b.Ymin && a.y<=b.Ymax) return 1; else return 0; } else return 0; } bool dfs(int pos,int u,int v) { for(int i=0;i<gr[pos].size();i++) { if(visit[gr[pos][i]] || (pos==u && v==gr[pos][i])) continue; visit[gr[pos][i]] = 1; if(rit[gr[pos][i]]==-1 || dfs(rit[gr[pos][i]],u,v)) { lef[pos] = gr[pos][i]; rit[gr[pos][i]] = pos; return 1; } } return 0; } int bipartite(int u,int v) { for(int i=0;i<105;i++) { lef[i]=-1;rit[i]=-1; } int res =0; for(int i=1;i<=N;i++) { memset(visit,0,sizeof(visit)); if(dfs(i,u,v)) res+=1; } return res; } int main() { int kase = 1; while(cin>>N) { if(!N) break; for(int i=1;i<=N;i++) { cin>>slide[i].Xmin>>slide[i].Xmax>>slide[i].Ymin>>slide[i].Ymax; gr[i].clear(); } for(int i=1;i<=N;i++) { cin>>pp[i].x>>pp[i].y; for(int j=1;j<=N;j++) { if(check(pp[i],slide[j])) gr[j].push_back(i); } } int res = bipartite(-1,-1); int ans[105]; for(int i=1;i<=N;i++) ans[i] = lef[i]; bool space = false; cout<<"Heap "<<kase++<<"\n"; for(int i=1;i<=N;i++) { if(bipartite(i,ans[i])<res) { if(space) cout<<" "; cout<<"("<<char(i+64)<<","<<ans[i]<<")";//cout<<"("<<char(ans[i]+64)<<","<<i<<")";// space = 1; } } if(!space) cout<<"none"; cout<<"\n\n"; } return 0; } |