题目信息

题目类型
练习
题目年份
2025
题目题型
编程题
关 键 词
求解二部图最大匹配的匈牙利算法

题目题干

求解二部图最大匹配的匈牙利算法

请编写程序,实现求解无权二部图最大匹配的匈牙利算法。jRq100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

输入格式:

输入首先在第一行给出 3 个正整数,依次为二部图 G=(U∪V,E) 中 U 点集顶点数、V 点集顶点数(均不超过 100)和边数 m。jRq100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
随后 m 行,每行给出一条连接 U 点集顶点和 V 点集顶点的边,格式为 u v,其中 u 属于 U,v 属于 V。两个点集的顶点编号均从 0 开始。同行数字间以一个空格分隔。jRq100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

输出格式:

在一行中输出 最大匹配值 = x,其中 x 为最大匹配数。jRq100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

输入样例:

4 3 7
0 0
0 1
1 1
1 2
2 0
2 1
3 2

输出样例:

最大匹配值 = 3

答案解析

相关题目

旅游规划有了一张自驾旅游路线图,你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序,帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的,那么需要
求解二部图最大匹配的匈牙利算法请编写程序,实现求解无权二部图最大匹配的匈牙利算法。 输入格式: 输入首先在第一行给出 3 个正整数,依次为二部图 G=(U∪V,E) 中 U 点集顶点数、V 点集顶点
求图中关键活动求图中关键活动请编写程序,实现求带权的有向图中关键活动的算法。 输入格式: 输入首先在第一行给出两个正整数,依次为当前要创建的图的顶点数 n(≤100)和边数 m。 随后 m 行,每行
拓扑排序请编写程序,实现对有向无权图中的顶点进行拓扑排序的算法。 注意:如果拓扑序不唯一,输出任何一个序列都可以,由特殊裁判程序判定正确性。 输入格式: 输入首先在第一行给出两个正整数,依次为当前要
求最小生成树的Prim算法请编写程序,实现在带权的无向图中求最小生成树的 Prim 算法。 注意:当多个待收录顶点到当前点集的距离等长时,按编号升序进行收录。 输入格式: 输入首先在第一行给出两个正
求所有点对间最短路的Floyd-Warshall算法请编写程序,实现在带权有向图中求所有点对间最短路的 Floyd-Warshall 算法。 输入格式: 输入首先在第一行给出两个正整数,依次为当前要
求单源最短路的Bellman-Ford算法请编写程序,实现在带负值权的有向图中求单源最短路的 Bellman-Ford 算法。 输入格式: 输入首先在第一行给出两个正整数,依次为当前要创建的图的顶点
求单源最短路的Dijkstra算法请编写程序,实现在带权的有向图中求单源最短路的 Dijkstra 算法。 注意:当多个待收录顶点路径等长时,按编号升序进行收录。 输入格式: 输入首先在第一行给出两
哥尼斯堡的“七桥问题” 哥尼斯堡是位于普累格河上的一座城市,它包含两个岛屿及连接它们的七座桥,如下图所示。 可否走过这样的七座桥,而且每桥只走过一次?瑞士数学家欧拉(Leonhard Euler
哥尼斯堡的“七桥问题” 哥尼斯堡是位于普累格河上的一座城市,它包含两个岛屿及连接它们的七座桥,如下图所示。 可否走过这样的七座桥,而且每桥只走过一次?瑞士数学家欧拉(Leonhard Euler

提示声明

  • 免责声明:本站资源均来自网络或者用户投稿,仅供用于学习和交流:如有侵权联系删除!
  • 温馨提示:本文属于积分文章,需要充值获得积分或升级VIP会员,也可在会员中心投稿获取。

猜你喜欢