题目描述给定若干幻灯片透明胶片每张幻灯片有一个矩形边界且上面写有一个数字数字编号从111开始。由于幻灯片重叠且透明我们无法直接看到哪个数字在哪个幻灯片上但可以通过位置关系推断如果一个数字位于某张幻灯片的矩形内部则该数字可能属于该幻灯片。每个数字恰好属于一张幻灯片且每个幻灯片恰好有一个数字。需要找出所有能够唯一确定其数字的幻灯片即该幻灯片在所有可能的合法匹配中只能对应同一个数字。若没有可唯一确定的输出none。输入格式多组数据。每组第一行为一个整数nnnn≤26n \le 26n≤26表示幻灯片数量。接下来nnn行每行四个整数xminx_{min}xmin​、xmaxx_{max}xmax​、yminy_{min}ymin​、ymaxy_{max}ymax​表示第iii张幻灯片标签从A开始的矩形边界。随后nnn行每行两个整数表示数字111到nnn的坐标。输入以n0n0n0结束。输出格式对于每组数据输出Heap X:其中XXX为数据组编号从111开始。然后输出所有可唯一确定的幻灯片及其对应的数字格式为(A,4)按幻灯片字母升序排列。若没有则输出none。每组输出后跟一个空行。样例输入4 6 22 10 20 4 18 6 16 8 20 2 18 10 24 4 8 9 15 19 17 11 7 21 11 2 0 2 0 2 0 2 0 2 1 1 1 1 0输出Heap 1 (A,4) (B,1) (C,2) (D,3) Heap 2 none题目分析本题可建模为二分图匹配问题。左侧是nnn个数字编号111到nnn右侧是nnn张幻灯片标签A到Z。若数字iii位于幻灯片jjj的矩形内则存在一条边(i,j)(i, j)(i,j)。问题的目标是给定二分图找出所有右侧节点幻灯片使得在所有完美匹配中该节点只能匹配同一个左侧节点数字。解决方法是先求出一个完美匹配最大匹配数应为nnn。然后对于每条边(j,i)(j, i)(j,i)即幻灯片iii可能匹配数字jjj临时删除该边再求最大匹配。若最大匹配数小于nnn则说明该边是唯一匹配即幻灯片iii必须对应数字jjj可以确定。最后按幻灯片标签升序输出所有可确定的配对。解题思路建图对于每个数字iii和每张幻灯片jjj如果points[i]在rectangles[j]内严格内部不落在边界则在二分图中添加边g[j][i]1g[j][i] 1g[j][i]1注意代码中ggg的行对应幻灯片列对应数字。求完美匹配使用匈牙利算法求最大匹配因为n≤26n \le 26n≤26复杂度很低。确定唯一配对对每张幻灯片jjj左部节点对每个数字iii右部节点如果边存在则删除该边重新求最大匹配。若匹配数小于nnn则说明该边是所有完美匹配都必须包含的因此幻灯片jjj唯一对应数字iii。输出按幻灯片标签升序即jjj从小到大收集所有唯一配对输出(letter, number)。若没有输出none。注意匈牙利算法中左部是幻灯片000到n−1n-1n−1右部是数字000到n−1n-1n−1。输出时幻灯片标签为Aj数字为i1。复杂度分析匈牙利算法O(n3)O(n^3)O(n3)n≤26n \le 26n≤26。对每条边最多n2676n^2 676n2676条都重新运行一次匈牙利算法总复杂度O(n5)O(n^5)O(n5)但nnn很小完全可接受。代码实现// Sorting Slides// UVa ID: 663// Verdict: Accepted// Submission Date: 2016-11-07// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintMAXV60;intg[MAXV][MAXV],visited[MAXV],cx[MAXV],cy[MAXV];inttx,ty;intdfs(intu){for(intv0;vty;v)if(g[u][v]!visited[v]){visited[v]1;if(cy[v]-1||dfs(cy[v])){cx[u]v;cy[v]u;return1;}}return0;}inthungarian(){memset(cx,-1,sizeof(cx));memset(cy,-1,sizeof(cy));intmatches0;for(inti0;itx;i)if(cx[i]-1){memset(visited,0,sizeof(visited));matchesdfs(i);}returnmatches;}structpoint{intx,y;};structrectangle{intxmin,xmax,ymin,ymax;};point points[MAXV];rectangle rectangles[MAXV];boolpointInBox(point p,rectangle r){returnp.xr.xminp.xr.xmaxp.yr.yminp.yr.ymax;}intmain(){intcases0;while(cinty,ty0){txty;for(inti0;ity;i){cinrectangles[i].xminrectangles[i].xmax;cinrectangles[i].yminrectangles[i].ymax;}for(inti0;itx;i)cinpoints[i].xpoints[i].y;memset(g,0,sizeof(g));for(inti0;itx;i)for(intj0;jty;j)if(pointInBox(points[i],rectangles[j]))g[i][j]1;coutHeap cases\n;booloutputedfalse;intmaxMatchhungarian();for(inti0;itx;i)for(intj0;jty;j)if(g[j][i]){g[j][i]0;intnextMatchhungarian();if(nextMatchmaxMatch){if(outputed)cout ;elseoutputedtrue;cout((char)(Ai),(j1));}g[j][i]1;}if(!outputed)coutnone;cout\n\n;}return0;}总结本题通过二分图匹配和“删除边后匹配数变化”的方法找出了所有在完美匹配中必然出现的配对。关键点包括正确建模为二分图左侧为幻灯片右侧为数字。利用匈牙利算法求最大匹配并判断是否完美。对每条边临时删除并重新匹配根据匹配数是否下降确定唯一性。输出格式按幻灯片字母升序。该解法是二分图匹配中“唯一匹配”判定的典型技巧适用于n≤26n \le 26n≤26的小规模问题。