文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 自然科学 > 数学 > 匈牙利,KM ,算法 模板
侵权投诉

匈牙利,KM ,算法 模板

匈牙利,KM ,算法  模板

匈牙利算法

令g=(x,*,y)是一个二分图,其中x={x1,x2...},y={y1,y2,....}.令m为g中的任意匹配。

1。将x的所有不与m的边关联的顶点表上¥,并称所有的顶点为未扫描的。转到2。

2。如果在上一步没有新的标记加到x的顶点上,则停,否则 ,转3

3。当存在x被标记但未被扫描的顶点时,选择一个被标记但未被扫描的x的顶点,比如xi,用(xi)标

记y 的所有顶点,这些顶点被不属于m且尚未标记的边连到xi。

现在顶点xi 是被扫描的。如果不存在被标记但未被扫描的顶点,转4。

4。如果在步骤3没有新的标记被标记到y的顶点上,则停,否则转5。

5。当存在y被标记但未被扫描的顶点时。选择y的一个被标记但未被扫描的顶点,比如yj,

用(yj)标记x的顶点,这些顶点被属于m且尚未标记的边连到yj。现在,顶点yj是被扫描的。

如果不存在被标记但未被扫描的顶点则转道2。

由于每一个顶点最多被标记一次且由于每一个顶点最多被扫描一次,本匹配算法在有限步内终止。 代码实现:

bfs过程:

#include<stdio.h>

#include<string.h>

main()

{

bool map[100][300];

int i,i1,i2,num,num1,que[300],cou,stu,match1[100],match2[300],pque,p1,now,prev[300],n;

scanf("%d",&n);

for(i=0;i<n;i++)

{

scanf("%d%d",&cou,&stu);

memset(map,0,sizeof(map));

for(i1=0;i1<cou;i1++)

{

scanf("%d",&num);

for(i2=0;i2<num;i2++)

{

第1页

你可能喜欢

热门文档

相关文档

  • 匈牙利算法和KM算法简介

    匈牙利,KM ,算法 模板 9页 1下载券 二分图匹配(匈牙利算法和... 9页 2...匈牙利算法求最大匹配的一种显而易见的算法是:先找出全部 匹配,然后保留匹配数...

  • 二分图(匈牙利,KM算法详解)

    二分图(匈牙利,KM算法详解)_计算机软件及应用_IT/计算机_专业资料。二分图算法的详解!很好理解二分图匹配 Bi-partite graph 二分图的定义: 二分图是这样的一...

  • 匈牙利算法和KM算法简介

    匈牙利,KM ,算法 模板 9页 2财富值 二分图匹配(匈牙利算法和K... 9页 ...完备匹配。 完备匹配 匈牙利算法求最大匹配的一种显而易见的算法是:先找出全部...

  • 匈牙利算法和KM算法

    匈牙利,KM ,算法 模板 9页 2财富值 匈牙利算法和KM算法简介 29页 免费 二... 匈牙利算法和 KM 算法 匈牙利算法 function dfs(k:longint):boolean; var i,...

  • 图的匹配——匈牙利算法与KM算法

    图的匹配——匈牙利算法与KM算法_IT/计算机_专业资料。二分图的最大匹配、最大权匹配、例题详解图的匹配一、什么是图的匹配 1.图的定义 无向图:无向图 G ...

  • 匈牙利算法和KM算法简介

    匈牙利算法和KM算法简介_数学_自然科学_专业资料。二分图匹配匈牙利算法和KM算法简介 二分图的概念 ? 二分图又称作二部图,是图论中的一种特殊 模型。 ? 设G...

  • 二分图匹配(匈牙利算法和KM算法)

    最大匹配,匈牙利算法 最大匹配,时间复杂度:O(VE) 原理: 寻找 M 的可增广轨 P,P 包含 2k+1 条边,其中 k 条属于 M,k+1 条不属于 M。修改 M ...

  • KM算法

    KM算法 noip 模板noip 模板隐藏>> Kuhn-Munkras算法流程: (1)初始化可行顶标的值 (2)用匈牙利算法寻找完备匹配 (3)若未找到完备匹配则修改可行顶标的值 (4...

  • 匈牙利算法

    匈牙利算法_计算机软件及应用_IT/计算机_专业资料。1. 学习匈牙利算法。基本模板是少不了的。贴一个模板试试(hdu 2063) #include<stdio.h> #include<string.h...

  • KM算法

    有了匈牙利算法的这个武器,KM 算法是很简单的。 程序照样短… {pro_bin of Kuhn-Munkres(KM) Algorithm O(n^3)} const maxn=100; var graph:array[1.....

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email