`
dogasshole
  • 浏览: 867259 次
文章分类
社区版块
存档分类
最新评论

http://acm.nyist.net/JudgeOnline/problem.php?pid=239

 
阅读更多

月老的难题

时间限制:1000 ms | 内存限制:65535 KB
难度:4
描述

月老准备给n个女孩与n个男孩牵红线,成就一对对美好的姻缘。

现在,由于一些原因,部分男孩与女孩可能结成幸福的一家,部分可能不会结成幸福的家庭。

现在已知哪些男孩与哪些女孩如果结婚的话,可以结成幸福的家庭,月老准备促成尽可能多的幸福家庭,请你帮他找出最多可能促成的幸福家庭数量吧。

假设男孩们分别编号为1~n,女孩们也分别编号为1~n。

输入
第一行是一个整数T,表示测试数据的组数(1<=T<=400)
每组测试数据的第一行有两个整数n,K,其中男孩的人数与女孩的人数都是n。(n<=500,K<=10 000)
随后的K行,每行有两个整数i,j表示第i个男孩与第j个女孩有可能结成幸福的家庭。(1<=i,j<=n)
输出
对每组测试数据,输出最多可能促成的幸福家庭数量
样例输入
1
3 4
1 1
1 3
2 2
3 2
样例输出
2

今天看了二分图最大匹配,感觉还行,首先存的时候用的是邻接表的方法,然后主要是找图中是不是有可增广路,如果存在就加一。这种就是所谓的匈牙利算法,看了看算法导论也可以转化为对应流网络的最大流问题。。对应的流网络就是在该图中添一个源点和汇点,即增加V条边,。

1.如果图G的顶点集V(G)能分成两个不想交的非空子集X和Y,使得G的每条边的两个端点分别在X和Y中,则称G为二分图。直观的讲就是X中的点互不邻接,Y中的点也互不邻接,而只有X和Y之间有边相邻的图。图1就是一个二分图:

最大二分匹配 - chhaj5236 - chhaj5236的博客最大二分匹配 - chhaj5236 - chhaj5236的博客

2.如果G的边集E(G)中有个子集M,满足M中的任何两条边都不邻接,则M就是图G的一个匹配。包含边数最多的匹配称为最大匹配,最大匹配所包含的边数称为最大匹配数。当G是二分图时,问题就比较特殊了,这就是我们后面要解决的问题——最大二分匹配。图二就是图一对应的一个最大二分匹配。

3.求解最大二分匹配可以通过网络流也可以通过匈牙利算法,下面我将会说明这两种方法的主要思想。


最大二分匹配可以很容易地转换成最大流问题,利用Ford-Fulkerson方法可以在关于|V|和|E|的多项式时间内,找出无向图G=(V,E)的最大匹配。解决这一问题的关键在于建立一个流网络,我们在原二分图的基础上引入两个新的节点s和t,分别作为源点和汇点,并重新构造整个流网络的边,将原二分图中的所有无向边(u,v)改成是从u指向v,并添加从s到X集合中所有顶点的有向边以及从Y集合中所有顶点到t的有向边,如图三:

最大二分匹配 - chhaj5236 - chhaj5236的博客

图三

最后将新图中的所有有向边的容量赋值为1,此时这个流网络对应的最大流的值和原二分图的最大匹配数就是相等的了。因为每条边的容量都是1,如果有一条增广路径是最大流的组成部分,那么这条路径贡献的流值就是1,而当贡献完这仅有的1个流值后,这条增光路径上的任何一条边从源点到汇点的方向就不再连通了。根据这个特性和二分图的特性,最大流f一定是由|f|条从s到t的互不相交的增广路径组成的,且每条增广路径的贡献均为1。观察图三,假设已知图三中二分图的某个最大匹配M,那么我们可以取最大匹配中的每条边、s与边在X中顶点的连线以及t与边在Y中的顶点的连线,显然这就组成了一个值为|M|的流。如果在该流网络中还存在一个比|M|更大的流|f|的话,我们显然可以将每条增广路径包含s和包含t的边去掉,而必定剩下|f|条互不相邻的边,且这|f|条边是满足匹配的条件的,就与|M|是最大匹配矛盾了,所以经过之前所讲的变化后就可以得到一个最大流与原二分图最大二分匹配相等的流网络了。具体实现参考Ford-Fulkerson求解最大流


在介绍匈牙利算法之前还是先提一下几个概念,下面M是G的一个匹配。 M-交错路:p是G的一条通路,如果p中的边为属于M中的边与不属于M但属于G中的边交替出现,则称p是一条M-交错路。如:路径(X3,Y2,X1,Y4),(Y1,X2,Y3)。 M-饱和点:对于v∈V(G),如果v与M中的某条边关联,则称v是M-饱和点,否则称v是非M-饱和点。如X1,X2,Y1,Y2都属于M-饱和点,而其它点都属于非M-饱和点。 M-可增广路:p是一条M-交错路,如果p的起点和终点都是非M-饱和点,则称p为M-可增广路。如(X3,Y2,X1,Y4)。(不要和流网络中的增广路径弄混了)

最大二分匹配 - chhaj5236 - chhaj5236的博客

图四

由于M-交错路由属于M和不属于M的边交替组成的,而M-可增广路的起始边和结束边都不属于M,所以M-可增广路的长度必定是奇数。假设p中属于M中边的条数为n,那么不属于M中的边就是n+1条,当找到p这条M-可增广路时,我们就将匹配由原来的M换成不属于M的n+1条边,显然这n+1条边也是符合匹配条件的,且比原匹配要大1。根据M-可增广路的这个性质,我们可以很容易的得到一个定理:图G的匹配M是最大匹配当且仅当G中不存在M-可增广路

匈牙利算法的本质思想就在于上面的定理,在图中寻找一条可增广路p,并将p中的边进行上述转换,得到一个新的匹配,然后再重复直到找不到可增广路为止。在具体实现时,我们从X集合中的点依次出发寻找可增广路,这样就能保证每次开始的起始点都是非M-饱和点,而对于Y集合中的点,我们维护一个数组match,如果match[i]不等于给定的初始值,就说明Y中标号为i的点与匹配M中的一条边关联,且另一个顶点在X中的标号为match[i]。所以当我们从X中的顶点u搜索可增光路时,如果与u相连的v还没有被匹配,那么肯定可以将(u,v)并入匹配M中,否则就通过(u,v,match[v])这条M-交错路回到X集合中,再从match[v]继续搜索。如果能够找到可增广路,就根据可增广路更新match数组。

这里还有一个问题,依次对X中的点进行上述的操作,会不会出现从某一个顶点找不到可增广路,但是经过后操作顶点对匹配的更新,而导致再从这个顶点出发又可以找到可增广路了呢?答案是不会。假设经过后操作顶点更新后,顶点u原本找不到可增广路,而现在对应了一条可增广路p,我们假设在第一次对u查找时与p中的一一对应的不可增广路为p',那么这条可增广路肯定是将p'中的某段M-交错路反向得到的。那么在这段M-交错路的左右相邻的两条边是什么情况呢,由于p'不是可增广路,所以左边和右边肯定分别和M-交错路的左右两边一条属于匹配M一条不属于,那么在反向后肯定就会在左右两边出现要不都属于M要不都不属于M,而由于p是一条可增广路,所以都属于的情况是不会出现的,只有都不属于,那么就会出现M-交错路加上左右两条边后,就形成了一条可增广路,显然这与p'是非可增广路矛盾了。这个证明比较绕,我也想了很久,可以画几个图来看一下,就会比较好理解了。

AC代码;


分享到:
评论

相关推荐

    在线OJ网址大全在线OJ网址大全

    14. **厦门大学SundayClub**(&lt;http://acm.sundayclub.cn/JudgeOnline/problemlist&gt;) - **特点**:题库更新及时,适合短期集训。 - **适用人群**:适合参加短期集训的学员。 15. **杭州师范大学**(...

    ACM学习资料汇总,ACMer要试试哦!

    - [题目1](http://acm.pku.edu.cn/JudgeOnline/problem?id=1141) —— 这是一道简单的动态规划题目,适合初学者练习。 2. **中等难度题目:** - [题目2](http://acm.pku.edu.cn/JudgeOnline/problem?id=2288) ——...

    《算法艺术与信息学竞赛》在pku等网站上的题目

    - **简单动态规划题目**:如题目[2288](http://acm.pku.edu.cn/JudgeOnline/problem?id=2288),这类题目通常用于动态规划的入门练习,旨在帮助初学者理解状态定义和状态转移的基本概念。 - **经典TSP问题**:题目...

    学习C语言的好网站和在线裁判系统 一些网站

    - 中国科学技术大学(USTC):http://acm.ustc.edu.cn/index.php - 西班牙瓦拉多利德大学(UV):http://acm.uva.es/ - 俄罗斯托木斯克国立大学(URAL):http://acm.timus.ru/ - 白俄罗斯国立大学(SGU):...

    算法分析与设计-大型实验报告样本

    浙江大学在线题库:http://acm.zju.edu.cn/problems.php 浙江工业大学在线题库:http://acm.zjut.edu.cn 衡阳市第八中学信息学奥赛论坛&zju译题站:http://61.187.179.132:82/ UVA在线题库:...

    ACM网站大全(OJ+代码+贴吧)

    - **北京大学 (PKU)**:`http://acm.pku.edu.cn/JudgeOnline/` - 北京大学的在线评测系统,也是国内最早的一批OJ平台之一。 - **杭州电子科技大学 (HDOJ)**:`http://acm.hziee.edu.cn/` - 杭州电子科技大学的在线...

    Web Navigation

    Assume that the browser initially loads the web page at the URL http://www.acm.org/ Input Input is a sequence of commands. The command keywords BACK, FORWARD, VISIT, and QUIT are all in uppercase. ...

    PLDI 2011-ACM SIGPLAN conference on PLDI 2011

    (我现在主要在CSDN上整理计算机安全、软件工程(可信软件)、系统及通信方面的论文及相关理论书籍,如果对这方面内容感兴趣,可以访问:http://qysh123.download.csdn.net/ 查看我上传的所有资料。内容比较多,需要...

    ACM网站大全

    - **网址**:http://acm.pku.edu.cn/JudgeOnline/problemlist - **简介**:这是一个著名的在线编程评测系统,提供大量经典的ACM题目,适合初学者及有经验的选手练习。 2. **浙江省信息学竞赛资源网** - **...

    ACM必备书籍及相关网站地址

    11. **北京大学在线评测系统**:[http://acm.pku.edu.cn/JudgeOnline/index.acm](http://acm.pku.edu.cn/JudgeOnline/index.acm) - 北京大学的在线评测系统,收录了大量的ACM竞赛题目。 12. **浙江大学在线评测...

    poj 图论 集合

    - **题目链接**:[POJ2449](http://acm.pku.edu.cn/JudgeOnline/problem?id=2449) - **解法概述**:此题可通过 Dijkstra 算法结合 A* 搜索策略来求解。主要考察的是如何在有向图中找到两个顶点之间的最短路径问题。 ...

    https://acm.timus.ru/print.aspx?space=1&num=1002 题目答案

    In the present world you frequently meet a lot of call numbers and they are going to be longer and longer. You need to remember such a kind of numbers. One method to do it in an easy way is to assign ...

    acm程序设计的网站

    5. **宁波大学 (NIT)** - &lt;http://acm.nit.net.cn/&gt; - NIT的ACM平台以其独特的题目风格受到欢迎,适合想要挑战新颖问题的学生。 - 提供在线评测功能,能够即时反馈代码执行结果,有助于提高学生的编程技能。 6. *...

    数据挖掘资源列表

    4. **KDD CUP center**([http://www.sigkdd.org/kddcup/index.php](http://www.sigkdd.org/kddcup/index.php)): KDD Cup是由ACM SIGKDD组织的数据挖掘竞赛,提供了历年的比赛数据集。 5. **Google n-grams ...

    DP46题.doc

    pid=1231 和 http://acm.hdu.edu.cn/showproblem.php?pid=1003) 这个问题寻找数组中的最大连续子序列和。状态方程可以表示为:`sum[i]=max(sum[i-1]+a[i], a[i])`,或者采用双指针方法进行遍历计算。 4. **Largest...

    Android代码-TagRec

    TagRec won the best poster award @ Hypertext 2014 (HT'14) conference: http://ht.acm.org/ht2014/index.php?awards.poster TagRec is also a main part of the recommender systems in the Layers project ...

    ACM程序大赛有关知识

    - 厦门大学ACM网址:http://acm.xmu.edu.cn/JudgeOnline/problemList.php **国际资源**: - USACO网址:http://ace.delos.com/usacogate/ - ICPC官方网站:http://icpc.baylor.edu/icpc/ 对于参赛者来说,ACM程序...

Global site tag (gtag.js) - Google Analytics