匈牙利算法
简单来说，如果图中点可以被分为两组，并且使得所有边都跨越组的边界，则这就是一个二分图。准确的说，把一个图的顶点划分为两个不相交集U和V，使得每一条边都分别连接U、V中的顶点。如果存在这样的划分，则此图为一个二分图。
什么是匹配？
在图论中，一个匹配是一个边的集合，其中任意两条边都没有公共顶点。比如下图所示，红边所画的就是一个匹配。其中1、4、5、7称为匹配点，2、3、6、7称为未匹配点，1-5、4-7称为匹配边，其他黑色的边称为未匹配边。
什么是最大匹配？
一个图所有匹配中，所含匹配边数最多的匹配，称为这个图的最大匹配。
什么是完美匹配？
如果一个图的某一个匹配中，所有的顶点都是匹配点，那么它就是一个完美匹配。显然，完美匹配一定时最大匹配，但每个图并非都存在完美匹配。
那么如果求得最大匹配呢？这时候，我们就切入正题，来讲讲匈牙利算法。
匈牙利算法是基于Hall定理中充分性证明的思想，它是部图匹配最常见的算法，该算法的核心就是寻找增广路径，它是一种用增广路径求二分图最大匹配的算法。
假如有N个男生，M个女生要进行配对，每个人可能对多名异性有好感，如果一对男女互有好感，那么就可以把这一对撮合在一起，举个以下一张关系图的栗子，每一条连线都表示互有好感。
那么如何用匈牙利算法来实现最大匹配呢？
一：先试着给1号男生找妹子，发现第一个和他相连的1号女生还名花无主，连上一条蓝线。
二：接着给2号男生找妹子，发现第一个和他相连的2号女生名花无主，连上一条蓝线。
三：接下来是3号男生，可惜1号女生已经有主了怎么办呢？
我们尝试着给之前1号女生匹配的男生（也就是1号男生）另外分配一个妹子。
（黄色表示这条边被临时拆掉）
与1号男生相连的第二个女生是2号女生，但是2号女生也有主了，怎么办呢？我们再试着给2号女生的原配重新找个妹子（注意这个步骤和上面是一样的，这是一个递归的过程）
此时发现2号男生还能找到3号女生，那么之前的问题就迎刃而解了，回溯回去。2号男生找3号女生 1号男生找2号女生 3号男生找1号女生
最后的结果就是：
四：接下来是4号男生，可惜按照第三步的节奏没能给4号男生腾出一个妹子来了。
总结：从上面的匈牙利算法的流程来看，其中找妹子就是一个递归的过程，最关键在于一个腾字，其原则大概是：有机会上，没机会创造机会也要上
#include<stdio.h>
#include<string.h>
#define MAX 100
int n,m;
bool line[MAX][MAX];
bool used[MAX];
int girl[MAX];
bool find(int x)
{
for(int j=1;j<=m;j++)//扫描每一个妹子
if(line[x][j]==true&&used[j]==false)
//如果有暧昧关系，并且没有被标记过
{
used[j]=true;//以便于递归的时候，知道这个妹子被看中过。
if(girl[j]==0||find(girl[j]))
//名花无主或者能挪出个位置来，这里使用递归
{
girl[j]=x;
return true;
}
}
return false;
}
int main()
{
int cnt=0;
printf("请分别输入男生和女生的数量:");
scanf("%d %d",&n,&m);
int t;//有t对暧昧关系
printf("请输入有几对暧昧关系:");
scanf("%d",&t);
printf("请输入%d对暧昧关系:\n",t);
int x,y;
memset(line,false,sizeof(line));
memset(girl,0,sizeof(girl));//初始化girl没有和任何人配对
for(int i=0;i<t;i++)
{
scanf("%d %d",&x,&y);
line[x][y]=true;
}
for(int i=1;i<=n;i++)
{
memset(used,false,sizeof(used));
if(find(i))
cnt++;
}
printf("最大匹配数为:%d\n",cnt);
}
相关阅读
这标题，怎么感觉好像有点震惊体的意思了。先上代码： C++版： #include <iostream> using namespace std; int prime(int n); int main
关于点击这里->普里姆算法 克鲁斯卡尔算法百度到的解释是：克鲁斯卡尔算法是一种用来寻找最小生成树的算法。在剩下的所有未选取的
你是如何坚持读完《算法导论》这本书的？ 《算法导论》不够猛，答者顺便补充 “你是如何坚持读完《计算机编程的艺术》这本书的？”
人类会关注图中对象的形状，深度学习计算机系统所用的算法不一样，它会研究对象的纹理。图片中的动物轮廓是猫，但是猫披着大象皮肤纹理
基于深度学习的人脸识别算法简介Contrastive LossTriplet LossCenter LossA-Softmax Loss参考文献：简介 我们经常能从电影中看到各