`
Simone_chou
  • 浏览: 182714 次
  • 性别: Icon_minigender_2
  • 来自: 广州
社区版块
存档分类
最新评论

Sorting Slides(二分图最大匹配 + 匈牙利算法)

    博客分类:
  • POJ
 
阅读更多
Sorting Slides
Time Limit: 1000MS   Memory Limit: 10000K
Total Submissions: 3110   Accepted: 1203

Description

Professor Clumsey is going to give an important talk this afternoon. Unfortunately, he is not a very tidy person and has put all his transparencies on one big heap. Before giving the talk, he has to sort the slides. Being a kind of minimalist, he wants to do this with the minimum amount of work possible. 

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

The input consists of several heap descriptions. Each heap descriptions starts with a line containing a single integer n, the number of slides in the heap. The following n lines contain four integers xmin, xmax, ymin and ymax, each, the bounding coordinates of the slides. The slides will be labeled as A, B, C, ... in the order of the 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

For each heap description in the input first output its number. Then print a series of all the slides whose numbers can be uniquely determined from the input. Order the pairs by their letter identifier. 

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;
}

 

分享到:
评论

相关推荐

    mysql安装教程,mac,windows

    1、Mac 2、windows 3、下载MySQL 4、安装MySQL 5、使用MySQL

    生成可读取配置文件的独立运行jar程序IDEA模版工程

    周五刚躺下,前线打来语音要个下载文件的小程序,下载路径和下载码需要根据配置获取,程序需要在服务器执行。当然配置的设计是个人设计的,不然每次更新下载码都要重新出具jar包,太麻烦。多年没写独立运行的jar包了,翻阅了相关资料,最终还是功夫不负有心人。想着这种需求后续可能经常碰到,遂总结经验,整理成模版,为大家所用。 ————————————————————————————————— 原文链接:https://blog.csdn.net/xuanxiaochuan/article/details/137001184 根据文章创建的模版工程文件,下载后可直接编辑main方法,根据自己的需求自定义逻辑内容,编译后获取independent.jar文件,修改配置文件后,通过java -jar independent.jar 执行命令,正常执行。

    世界读书日ppt模板x.pptx

    世界读书日ppt模板x.pptx

    Week+5.ipynb

    Week+5.ipynb

    L型单极性单相逆变电路simulink仿真

    单极性单相逆变电路simulink仿真单极性单相逆变电路simulink仿真单极性单相逆变电路simulink仿真单极性单相逆变电路simulink仿真单极性单相逆变电路simulink仿真单极性单相逆变电路simulink仿真单极性单相逆变电路simulink仿真单极性单相逆变电路simulink仿真单极性单相逆变电路simulink仿真单极性单相逆变电路simulink仿真单极性单相逆变电路simulink仿真单极性单相逆变电路simulink仿真单极性单相逆变电路simulink仿真单极性单相逆变电路simulink仿真单极性单相逆变电路simulink仿真单极性单相逆变电路simulink仿真单极性单相逆变电路simulink仿真单极性单相逆变电路simulink仿真单极性单相逆变电路simulink仿真单极性单相逆变电路simulink仿真单极性单相逆变电路simulink仿真单极性单相逆变电路simulink仿真单极性单相逆变电路simulink仿真单极性单相逆变电路simulink仿真单极性单相逆变电路simulink仿真单极性单相逆变电路simulink仿真单极性单相逆

    pypy3.7-v7.3.8-aarch64-portable.tar.bz2

    Python库是一组预先编写的代码模块,旨在帮助开发者实现特定的编程任务,无需从零开始编写代码。这些库可以包括各种功能,如数学运算、文件操作、数据分析和网络编程等。Python社区提供了大量的第三方库,如NumPy、Pandas和Requests,极大地丰富了Python的应用领域,从数据科学到Web开发。Python库的丰富性是Python成为最受欢迎的编程语言之一的关键原因之一。这些库不仅为初学者提供了快速入门的途径,而且为经验丰富的开发者提供了强大的工具,以高效率、高质量地完成复杂任务。例如,Matplotlib和Seaborn库在数据可视化领域内非常受欢迎,它们提供了广泛的工具和技术,可以创建高度定制化的图表和图形,帮助数据科学家和分析师在数据探索和结果展示中更有效地传达信息。

    xx集团数字化转型方案ss.pptx

    xx集团数字化转型方案ss.pptx

    chatgpt免费使用.txt

    chatgpt免费使用

    超微 X11DPX-T主板用户手册

    超微 X11DPX-T主板用户手册

    tensorflow-2.6.2-cp36-cp36m-manylinux2010-x86-64.whl

    numpy安装

    pypy2.7-v7.2.0rc0-aarch64.tar.bz2

    Python库是一组预先编写的代码模块,旨在帮助开发者实现特定的编程任务,无需从零开始编写代码。这些库可以包括各种功能,如数学运算、文件操作、数据分析和网络编程等。Python社区提供了大量的第三方库,如NumPy、Pandas和Requests,极大地丰富了Python的应用领域,从数据科学到Web开发。Python库的丰富性是Python成为最受欢迎的编程语言之一的关键原因之一。这些库不仅为初学者提供了快速入门的途径,而且为经验丰富的开发者提供了强大的工具,以高效率、高质量地完成复杂任务。例如,Matplotlib和Seaborn库在数据可视化领域内非常受欢迎,它们提供了广泛的工具和技术,可以创建高度定制化的图表和图形,帮助数据科学家和分析师在数据探索和结果展示中更有效地传达信息。

    pypy2.7-v7.3.12rc2-s390x.tar.bz2

    Python库是一组预先编写的代码模块,旨在帮助开发者实现特定的编程任务,无需从零开始编写代码。这些库可以包括各种功能,如数学运算、文件操作、数据分析和网络编程等。Python社区提供了大量的第三方库,如NumPy、Pandas和Requests,极大地丰富了Python的应用领域,从数据科学到Web开发。Python库的丰富性是Python成为最受欢迎的编程语言之一的关键原因之一。这些库不仅为初学者提供了快速入门的途径,而且为经验丰富的开发者提供了强大的工具,以高效率、高质量地完成复杂任务。例如,Matplotlib和Seaborn库在数据可视化领域内非常受欢迎,它们提供了广泛的工具和技术,可以创建高度定制化的图表和图形,帮助数据科学家和分析师在数据探索和结果展示中更有效地传达信息。

    ddwrt.v24-vpn-generic.bin

    ddwrt.v24_vpn_generic.bin

    pypy3.7-v7.3.4-osx64.tar.bz2

    Python库是一组预先编写的代码模块,旨在帮助开发者实现特定的编程任务,无需从零开始编写代码。这些库可以包括各种功能,如数学运算、文件操作、数据分析和网络编程等。Python社区提供了大量的第三方库,如NumPy、Pandas和Requests,极大地丰富了Python的应用领域,从数据科学到Web开发。Python库的丰富性是Python成为最受欢迎的编程语言之一的关键原因之一。这些库不仅为初学者提供了快速入门的途径,而且为经验丰富的开发者提供了强大的工具,以高效率、高质量地完成复杂任务。例如,Matplotlib和Seaborn库在数据可视化领域内非常受欢迎,它们提供了广泛的工具和技术,可以创建高度定制化的图表和图形,帮助数据科学家和分析师在数据探索和结果展示中更有效地传达信息。

    《工业视觉检测平台的思考与应用》qy.pptx

    《工业视觉检测平台的思考与应用》qy.pptx

    输电线路涉鸟故障相关鸟种细粒度分类数据集(2889张+50类)

    内含输电线路涉鸟故障相关鸟种细粒度分类数据集,2889张图片,图像分类数据集,类别有50,可以用于电气工程专业在计算机视觉应用领域做研究,例如目标检测、图像识别、深度学习等!!! txt文件内有下载链接和提取码,放心下载即可!!!!

    毕业设计: Java项目springboot基于SpringBoot的医院药品管理系统(源码 + 数据库 + 论文)

    论文目录: 2 系统开发环境 3 2.1 vue技术 3 2.2 JAVA技术 3 2.3 MYSQL数据库 3 2.4 B/S结构 4 2.5 SSM框架技术 4 3 系统分析 5 3.1 可行性分析 5 3.1.1 技术可行性 5 3.1.2 操作可行性 5 3.1.3 经济可行性 5 3.1.4 法律可行性 5 3.2 系统性能分析 5 3.3 系统功能分析 6 3.3.1 角色需求 6 3.3.2 功能需求 6 3.4 系统流程分析 6 3.4.1 注册流程 6 3.4.2 登录流程 7 4 系统设计 8 4.1 系统概要设计 8 4.2 系统结构设计 8 4.3 数据库设计 9 4.3.1 数据库表设计 9 5 系统的实现 13 5.1 功能模块的实现 13 5.1用户信息管理 13 5.2 员工信息管理 14 5.3药品信息管理 16 5.1公告信息管理 18 6 系统测试 21 6.1 测试定义 21 6.2 测试目的 21 6.3 测试方法 21 6.4 测试分析 21

    OpenLane车道线数据集百度网盘链接(永久有效)

    总大小:114.39G OpenLane包含20万帧、超过88万条实例级车道、14个车道类别(单白色虚线、双黄色实体、左/右路边等),以及场景标签和路线邻近目标(CIPO)注释,以鼓励开发3D车道检测和更多与产业相关的自动驾驶方法。

    pypy2.7-v7.2.0-s390x.tar.bz2

    Python库是一组预先编写的代码模块,旨在帮助开发者实现特定的编程任务,无需从零开始编写代码。这些库可以包括各种功能,如数学运算、文件操作、数据分析和网络编程等。Python社区提供了大量的第三方库,如NumPy、Pandas和Requests,极大地丰富了Python的应用领域,从数据科学到Web开发。Python库的丰富性是Python成为最受欢迎的编程语言之一的关键原因之一。这些库不仅为初学者提供了快速入门的途径,而且为经验丰富的开发者提供了强大的工具,以高效率、高质量地完成复杂任务。例如,Matplotlib和Seaborn库在数据可视化领域内非常受欢迎,它们提供了广泛的工具和技术,可以创建高度定制化的图表和图形,帮助数据科学家和分析师在数据探索和结果展示中更有效地传达信息。

    ASCII码表 ASCII码表

    ASCII码表 ASCII码表 ASCII码表 ASCII码表 ASCII码表 ASCII码表 ASCII码表 ASCII码表 ASCII码表 ASCII码表 ASCII码表 ASCII码表 ASCII码表 ASCII码表 ASCII码表 ASCII码表 ASCII码表 ASCII码表 ASCII码表 ASCII码表 ASCII码表 ASCII码表 ASCII码表 ASCII码表 ASCII码表 ASCII码表 ASCII码表 ASCII码表 ASCII码表 ASCII码表 ASCII码表 ASCII码表 ASCII码表 ASCII码表 ASCII码表 ASCII码表 ASCII码表 ASCII码表 ASCII码表 ASCII码表 ASCII码表 ASCII码表 ASCII码表 ASCII码表 ASCII码表 ASCII码表 ASCII码表 ASCII码表 ASCII码表 ASCII码表 ASCII码表 ASCII码表 ASCII码表 ASCII码表 ASCII码表 ASCII码表 ASCII码表 ASCII码表

Global site tag (gtag.js) - Google Analytics