首页 > 代码库 > dfs模板 二部图的最大匹配

dfs模板 二部图的最大匹配

2024-11-21 09:11:39   202人阅读

  1. /****************************************************
  2. 二分图匹配（匈牙利算法的DFS实现）
  3. INIT：g[][]两边定点划分的情况
  4. CALL:res=hungary();输出最大匹配数
  5. 优点：适于稠密图，DFS找增广路快，实现简洁易于理解
  6. 时间复杂度:O(VE);
  8. 适用范围：
  9. 二分图的 最小顶点覆盖 ==== 最大匹配
  10. DAG图的 最小路径覆盖数 == 节点数 – 最大匹配数
  11. 二分图的 最大独立集数 = 节点数 – 最大匹配数
  12. ****************************************************/
  15. #include <string>
  16. #include <stdio.h>
  17. using namespace std;
  19. #define MAXN 1000
  21. int path[MAXN][MAXN];
  23. bool sign[MAXN];								//v是否已经匹配的标志
  25. int road[MAXN];									//匹配存在road中，从v->u的
  27. int u_num, v_num;								//两个集合各自的元素总数
  29. bool dfs(int u)
  30. {
  31. 	for(int v=0; v<=v_num; v++)					//这里加个等于号和题目有关
  32. 	{
  33. 		if(path[u][v] && !sign[v])				//path[u][v] 存在关联与否，与没有匹配的v结合
  34. 		{
  35. 			sign[v] = true;						//结合后的v设定为匹配
  36. 			if(road[v] == -1 || dfs(road[v]) )
  37. 			{
  38. 				road[v] = u;					//保存u->v的匹配路径	
  39. 				return true;
  40. 			}
  41. 		}
  42. 	}
  43. 	return false;
  44. }
  46. int hungray()
  47. {
  48. 	int match = 0;								//匹配数
  49. 	memset(road, -1, sizeof(road) );			//匹配路径初始化
  50. 	for(int u=0; u<=u_num; u++)
  51. 	{
  52. 		memset(sign, 0, sizeof(sign) );			//每查找一次u， v集合相应清空
  53. 		if(dfs(u) )		match++;
  54. 	}
  55. 	return match;
  56. }
  59. void input(int n)
  60. {
  61. 	memset(path, 0,sizeof(path) );
  62. 	for(int i=0; i<n; i++)
  63. 	{
  64. 		int u, v;
  65. 		scanf("%d%d", &u, &v);
  66. 		path[u][v] = 1;
  67. 	}
  68. }
  70. int main()
  71. {
  72. 	int n;
  73. 	while(scanf("%d")!=EOF)
  74. 	{
  75. 		scanf("%d%d", &u_num, &v_num);
  76. 		input(n);
  77. 		printf("%d\nn", hungray() );
  78. 	}
  79. 	return 0;
  80. }



来自为知笔记(Wiz)


附件列表

     

    dfs模板 二部图的最大匹配


    联系
    我们