Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 3110 | Accepted: 1203 |
Description
The situation is like this. The slides all have numbers written on them according to their order in the talk. Since the slides lie on each other and are transparent, one cannot see on which slide each number is written.
Well, one cannot see on which slide a number is written, but one may deduce which numbers are written on which slides. If we label the slides which characters A, B, C, ... as in the figure above, it is obvious that D has number 3, B has number 1, C number 2 and A number 4.
Your task, should you choose to accept it, is to write a program that automates this process.
Input
This is followed by n lines containing two integers each, the x- and y-coordinates of the n numbers printed on the slides. The first coordinate pair will be for number 1, the next pair for 2, etc. No number will lie on a slide boundary.
The input is terminated by a heap description starting with n = 0, which should not be processed.
Output
If no matchings can be determined from the input, just print the word none on a line by itself.
Output a blank line after each test case.
Sample Input
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
Sample Output
Heap 1 (A,4) (B,1) (C,2) (D,3) Heap 2 none
题意:
给出N,后给出 N 个区域,每个区域给出Xi,Xj,Yi,Yj,说明这个区域是Xi ~ Xj,Yi ~ Yj 区域的。后给出 N 个点,给出每个点的 X ,Y 坐标。每个坐标都对应有一个区域,问能不能确定某些点在某个区域中。每个区域开始到结束用A,B,C,D,……来表示,点用1,2,3,4,……来表示。能确定则输出对应关系。若任何点都不能确定则输出none。
思路:
二分图最大匹配。这题与之前的题不同,找的是二分图必须边。并且要明确题意。
每个点都会对应一个区域,相同的每个区域都会对应到一个值,所以这是满射的关系。现在要判断的是能不能确定下来每个点对应的是哪个区域。比如1号点对应的是A,B区域,2号点对应的也是A和B区域,那么就不能确定下来到底是1号点对应A区域还是2号点对应A区域了。
既然是满射的话,任何区域或者点的度数为1的点,该边就应该是确定的边了,换句话说就是二分图最大匹配不能缺少的一条边,若缺少了的话,最大匹配就会减少了。继续往下看,当找完这条边后,删除这条边,那么与该边相关联的度为2点,也会产生一条必须边,递推下去的话,就是不断找必须边的过程,那么要找的就是二分图的必须边了。既然是必须边的话,缺少的话,最大匹配就会减少。
而且,在这题还有隐含的条件就是满射,说明它的最大匹配就是 N。之后再枚举每条边,删除后匹配一次,匹配减少了的话,说明这条是必须边了,找的同时输出即可。找不到则输出none。
二分图必须边:
二分图必须边就是二分图最大匹配所不能缺少的边。这道题有个条件就是,度为1的点或者区域所关联的边就是必须边,但是在其他题中就不一定是了。若其他题也要找必须边的话,要先最大匹配一次,后再枚举每条边再匹配,若匹配减少了则说明这条边是必须边。
AC:
#include <cstdio> #include <algorithm> #include <string.h> using namespace std; int n; int r[200][5],w[200][200]; int vis[200],linker[200]; bool dfs(int u) { for(int v = 1;v <= n;v++) if(w[u][v] && !vis[v]) { vis[v] = 1; if(linker[v] == -1 || dfs(linker[v])) { linker[v] = u; return true; } } return false; } int hungary() { int res = 0; memset(linker,-1,sizeof(linker)); for(int u = 1;u <= n;u++) { memset(vis,0,sizeof(vis)); if(dfs(u)) res++; } return res; } int main() { int time = 0; while(~scanf("%d",&n) && n) { ++time; memset(w,0,sizeof(w)); for(int i = 1;i <= n;i++) for(int j = 1;j <= 4;j++) scanf("%d",&r[i][j]); for(int i = 1;i <= n;i++) { int x,y; scanf("%d%d",&x,&y); for(int j = 1;j <= n;j++) if(x >= r[j][1] && x <= r[j][2] && y >= r[j][3] && y <= r[j][4]) { w[j][i] = 1; } } printf("Heap %d\n",time); int sum = 0; for(int i = 1;i <= n;i++) for(int j = 1;j <= n;j++) { if(w[i][j]) { w[i][j] = 0; if(hungary() < n) { if(!sum) printf("(%c,%d)",'A' + i - 1,j); else printf(" (%c,%d)",'A' + i - 1,j); sum++; } w[i][j] = 1; } } if(!sum) printf("none\n\n"); else printf("\n\n"); } return 0; }
相关推荐
这是一个实现不同排序算法的简单C ++模板库。 目标 该项目的目标是学习不同的规范排序算法及其实现; 这纯粹是教育性的。 我没有对它们进行任何优化研究,因此,可能会有更快(但更复杂)的实现方法。 我确实在实现...
cplusplus排序算法在2020年秋季学期的数据结构课程结束时,我们学习了各种排序算法,以及排序算法在计算机科学中的重要性。 结果,我决定为自己编写每种排序算法的代码,以希望我能对每种算法有深入的了解。 该排序...
排序算法 该存储库包含几种排序算法的实现。 使用C ++语言,结合使用开发的图形库构建算法,以便在算法运行时进行可视化。 怎么跑 完成项目克隆后,将sfml库下载到您的计算机上(仅对于debian / ubuntu OS,请在此...
北大POJ1094-Sorting It All Out 解题报告+AC代码
排序算法 在C / C ++中实现四种键排序算法。 四种排序算法是插入排序,选择排序,Shell排序和快速排序。 快速排序实现是“ SortComparisonView.cpp”文件中插入排序和快速排序之间比较的一部分。 作为上述文件中...
running_video.mp4 排序可视化器 借助C ++和图形,可以以直方图方式显示排序技术
Sorting and Searching Algorithms:A Cookbook 常用算法数据结构
随机数列,可控制上下界线。冒泡算法,c++,bubble sorting
Java实现常用sorting算法,包括insertion, merge, bubble, heap, quick, couting, radix, bucket and maxHeap/Priority queue sorting。并对算法复杂度使用场景做了分析。 主要参考资料wikipedia, CLRS算法教材
all kinds of sortings
大脑都快生锈了,写些基础算法。我的博客中的“基础算法与实现(一)——排序算法”中包含了:冒泡排序 选择排序 快速排序 堆排序 归并排序 开发环境是Linux ubuntu,含有Makefile文件,欢迎大家阅读评论,共同学习...
javascript、sorting、algorithm
算法参考资料Algorithms in C++, Parts 1-4 Fundamentals, Data Structure, Sorting, Searching (3rd Edition)提取方式是百度网盘分享地址
JavaScript_使用javascript开发的排序算法_sorting
PHP_使用php实现的排序算法_Sorting
ruby_使用ruby实现的排序算法_sorting
快速排序sorting
生成一个可以控制上下界限的随机数列,并使用选择排序selection sorting算法对其排序。
排序实现 内部排序的C ++实现。 撰写人: 气泡排序 按计数排序 通过二进制堆排序 按插入排序 合并排序 快速分类 按选择排序 振动筛分选 壳排序(随着距离的减小) 用二叉搜索树排序
Algorithm-sorting-visualization.zip,生成gif的命令行工具,可以显示排序算法,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。