{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":" \n \u003cp\u003e上一回我们已经将所有有问题的相亲情况表剔除了,那么接下来要做的就是安排相亲了。因为过年时间并不是很长,所以姑姑希望能够尽可能在一天安排比较多的相亲。由于一个人同一天只能和一个人相亲,所以要\u003cstrong\u003e从当前的相亲情况表里选择尽可能多的组合,且每个人不会出现两次\u003c/strong\u003e。不知道有没有什么好办法,对于当前给定的相亲情况表,能够算出最多能同时安排多少组相亲呢?\u003c/p\u003e \n \u003cp\u003e同样的,我们先将给定的情况表转换成图G\u003d(V,E)。在上一回中我们已经知道这个图可以被染成黑白两色。不妨将所有表示女性的节点记为点集A,表示男性的节点记为点集B。则有A∪B\u003dV。由问题可知所有边e的两个端点分别属于AB两个集合。则可以表示成如下的图: \u003c/p\u003e \n \u003cp style\u003d\"text-align:center;\"\u003e\u003cimg title\u003d\"hiho34_00.png\" style\u003d\"width:20%;\" src\u003d\"CDN_BASE_URL/7449fa172e14ca2033271508e0f9ad96?v\u003d1659858450\"\u003e\u003c/p\u003e \n \u003cp\u003e同样的,我们将所有的边分为两个集合。集合S和集合M,同样有S∪M\u003dE。边集S表示在这一轮相亲会中将要进行的相亲,边集M表示在不在这一次进行。对于任意边(u,v) ∈ S,我们称u和v为一组匹配,它们之间相互匹配。在图G,我们将边集S用实线表示,边集M用虚线表示。得到下图: \u003c/p\u003e \n \u003cp style\u003d\"text-align:center;\"\u003e\u003cimg title\u003d\"hiho34_01.png\" style\u003d\"width:20%;\" src\u003d\"CDN_BASE_URL/ab828a9790e64babe5128d6f96066586?v\u003d1659858450\"\u003e\u003c/p\u003e \n \u003cp\u003e则原问题转化为,最多能选择多少条边到集合S,使得S集合中任何两条边不相邻(即有共同的顶点)。显然的,|S|\u0026lt;\u003dMin{|A|, |B|}。 \u003c/p\u003e \n \u003cp\u003e那么能不能找到一个算法,使得能够很容易计算出尽可能多的边能够放入集合S?我们不妨来看一个例子: \u003c/p\u003e \n \u003cp style\u003d\"text-align:center;\"\u003e\u003cimg title\u003d\"hiho34_01.png\" style\u003d\"width:20%;\" src\u003d\"CDN_BASE_URL/ab828a9790e64babe5128d6f96066586?v\u003d1659858450\"\u003e\u003c/p\u003e \n \u003cp\u003e对于已经匹配的点我们先不考虑,我们从未匹配的点来做。这里我们选择A集合中尚未匹配的点(A3和A4)考虑: \u003c/p\u003e \n \u003cp\u003e对于A3点,我们可以发现A3与B4右边相连,且都未匹配。则直接将(A3,B4)边加入集合S即可。 \u003c/p\u003e \n \u003cp style\u003d\"text-align:center;\"\u003e\u003cimg title\u003d\"hiho34_02.png\" style\u003d\"width:20%;\" src\u003d\"CDN_BASE_URL/688937216695a13181681b513d9f1ce6?v\u003d1659858450\"\u003e\u003c/p\u003e \n \u003cp\u003e对于A4点,我们发现和A4相连的B3,B4点都已经匹配了。但是再观察可以发现,如果我们将A2和B2相连,则可以将B3点空出来。那么就可以同时将(A2,B2),(A4,B3)相连。将原来的一个匹配变成了两个匹配。 \u003c/p\u003e \n \u003cp\u003e让我们来仔细看看这一步:我们将这次变换中相关联的边标记出来,如下图所示紫色的3条边(A2,B2),(A2,B3),(A4,B3)。 \u003c/p\u003e \n \u003cp style\u003d\"text-align:center;\"\u003e\u003cimg title\u003d\"hiho34_03.png\" style\u003d\"width:20%;\" src\u003d\"CDN_BASE_URL/9111a03cd5859a58a72aea7c856971fd?v\u003d1659858450\"\u003e\u003c/p\u003e \n \u003cp\u003e这三条边构成了一条路径,可以发现这条路径有个非常特殊的性质。\u003cstrong\u003e虚线和实线相互交错,并且起点和终点都是尚未匹配的点,且属于两个不同的集合。我们称这样的路径为交错路径。 \u003c/strong\u003e\u003c/p\u003e \n \u003cp\u003e再进一步分析,对于任意一条交错路径,虚线的数量一定比实线的数量多1。我们将虚线和实线交换一下,就变成了下面的图: \u003c/p\u003e \n \u003cp style\u003d\"text-align:center;\"\u003e\u003cimg title\u003d\"hiho34_04.png\" style\u003d\"width:20%;\" src\u003d\"CDN_BASE_URL/8a129b94565e23b9dc304b1edda32cbd?v\u003d1659858450\"\u003e\u003c/p\u003e \n \u003cp\u003e在原来1个匹配的基础上,我们得到了2个新的匹配,S集合边的数量也增加了1。并且原来在已经匹配的点仍然是已经匹配的状态。 \u003c/p\u003e \n \u003cp\u003e再回头看看A3点匹配时的情况:对于(A3,B4)这一条路径,同样满足了交错路径的性质。 \u003c/p\u003e \n \u003cp\u003e至此我们得到了一个找新匹配的有效算法: \u003c/p\u003e \n \u003cp\u003e选取一个未匹配的点,查找是否存在一条以它为起点的交错路径。若存在,将该交错路径的边虚实交换。否则在当前的情况下,该点找不到可以匹配的点。 \u003c/p\u003e \n \u003cp\u003e又有对于已经匹配的点,该算法并不会改变一个点的匹配状态。所以当我们对所有未匹配的点都计算过后,仍然没有交错路径,则不可能找到更多的匹配。此时S集合中的边数即为最大边数,我们称为最大匹配数。 \u003c/p\u003e \n \u003cp\u003e那么我们再一次梳理整个算法: \u003c/p\u003e \n \u003cp\u003e1. 依次枚举每一个点i; \u003cbr\u003e2. 若点i尚未匹配,则以此点为起点查询一次交错路径。 \u003c/p\u003e \n \u003cp\u003e最后即可得到最大匹配数。 \u003c/p\u003e \n \u003cp\u003e在这个基础上仍然有两个可以优化的地方: \u003c/p\u003e \n \u003cp\u003e1.对于点的枚举:当我们枚举了所有A中的点后,无需再枚举B中的点,就已经得到了最大匹配。\u003cbr\u003e2.在查询交错路径的过程中,有可能出现Ai与Bj直接相连,其中Bj为已经匹配的点,且Bj之后找不到交错路径。之后又通过Ai查找到了一条交错路径{Ai,Bx,Ay,…,Az,Bj}延伸到Bj。由于之前已经计算过Bj没有交错路径,若此时再计算一次就有了额外的冗余。所以我们需要枚举每个Ai时记录B集合中的点是否已经查询过,起点不同时需要清空记录。 \u003c/p\u003e\u003c!-- Button trigger modal --\u003e \n \u003cp style\u003d\"margin-top:10px;\"\u003e\u003ca href\u003d\"#\" data-toggle\u003d\"modal\" data-target\u003d\"#m1\"\u003e伪代码\u003c/a\u003e\u003c/p\u003e\u003c!-- Modal --\u003e \n \u003cdiv tabindex\u003d\"-1\" class\u003d\"modal\" id\u003d\"m1\" role\u003d\"dialog\" aria-hidden\u003d\"true\" aria-labelledby\u003d\"myModalLabel\"\u003e \n \u003cdiv class\u003d\"modal-dialog\"\u003e \n \u003cdiv class\u003d\"modal-content\"\u003e \n \u003cdiv class\u003d\"modal-header\"\u003e \u003cbutton class\u003d\"close\" aria-label\u003d\"Close\" type\u003d\"button\" data-dismiss\u003d\"modal\"\u003e\u003cspan aria-hidden\u003d\"true\"\u003e×\u003c/span\u003e\u003c/button\u003e \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \n \u003ch4 class\u003d\"modal-title\" id\u003d\"myModalLabel\"\u003e伪代码\u003c/h4\u003e \n \u003c/div\u003e \n \u003cdiv class\u003d\"modal-body\"\u003e \n \u003cp\u003eFunction FindPath(u)\u003cbr\u003e \u0026nbsp; \u0026nbsp; For v∈u的相邻节点\u003cbr\u003e \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp;标记v已经查询过\u003cbr\u003e \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp;If v未匹配 or FindPath(v的匹配的点) Then\u003cbr\u003e \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; 更改u的匹配为v\u003cbr\u003e \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; Return Ture\u003cbr\u003e \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; End If\u003cbr\u003e \u0026nbsp; \u0026nbsp; End For\u003cbr\u003e Return False\u003cbr\u003e\u003cbr\u003e For i ∈ V\u003cbr\u003e \u0026nbsp; \u0026nbsp; 清空标记\u003cbr\u003e \u0026nbsp; \u0026nbsp;FindPath(i)\u003cbr\u003e End If\u003c/p\u003e \n \u003c/div\u003e \n \u003cdiv class\u003d\"modal-footer\"\u003e \u003cbutton class\u003d\"btn btn-default\" type\u003d\"button\" data-dismiss\u003d\"modal\"\u003eClose\u003c/button\u003e \u0026nbsp; \u0026nbsp; \u0026nbsp; \n \u003cbr\u003e \n \u003c/div\u003e \u0026nbsp; \n \u003c/div\u003e \n \u003c/div\u003e \n \u003c/div\u003e \n "}},{"title":"Input","value":{"format":"HTML","content":" \n \u003cp\u003e第1行:2个正整数,N,M(N表示点数 2≤N≤1,000,M表示边数1≤M≤5,000)\u003cbr\u003e第2..M+1行:每行两个整数u,v,表示一条无向边(u,v)\u003c/p\u003e \n "}},{"title":"Output","value":{"format":"HTML","content":" \n \u003cp\u003e第1行:1个整数,表示最大匹配数\u003c/p\u003e \n \u003c/div\u003e \n "}},{"title":"Sample Input","value":{"format":"HTML","content":" \n \u003cpre\u003e5 4\r\n3 2\r\n1 3\r\n5 4\r\n1 5\u003c/pre\u003e \n "}},{"title":"Sample Output","value":{"format":"HTML","content":" \n \u003cpre\u003e2\u003c/pre\u003e \n "}}]}