匈牙利算法
本文内容大部分参考Dark_Scope《趣写算法系列之–匈牙利算法 》
这是一个有趣的算法。没有复杂的技巧，只是几句循环判断
形象地说，在这个算法中，我们充当的是媒婆的角色，帮助两方的角色进行匹配。
匈牙利算法是一种在多项式时间内求解任务分配问题的组合优化算法，并推动了后来的原始对偶方法。美国数学家哈罗德·库恩于1955年提出该算法。此算法之所以被称作匈牙利算法，是因为算法很大一部分是基于以前匈牙利数学家Dénes Kőnig$和Jenő Egerváry的工作之上创建起来的。
—— By 著名权威学者-百度词条
理解
举个比较实际的栗子
lzh非常喜欢立Flag，他成立了自己的立Flag团（一下简称F团）。今天F团团长lzh又招到了新人手，lzh开始感到麻烦了，因为他不知道怎样给F团的新成员们分配flag。
lzh给新成员们展示了可供分配的flag，然后询问了每个新成员的心仪的flag。他找到了你，想让你解决这个分配问题。lzh会提供给你可供分配的旗帜信息、每个成员的信息和他们的心仪flag。保证没有哪个不可描述的成员会对未提供的flag感兴趣。
于是乎，我们现在需要做的就是给F团的新成员分配flag并且最好让每个人都能拿到自己喜欢的flag。我们可以把这个问题先抽象成一张图来：把人和旗帜先分成两队。
我们假设滑稽1，2喜欢爆0（暴少了个火字旁实在抱歉），滑稽1喜欢溢出，滑稽1，2，3，4都喜欢AK-IOI，于是可得出关系图。图中黄色的先表示喜欢（当然是理解为有向，只有人会喜欢flag，flag不会喜欢人的）
开始分配旗帜，首先把滑稽1所心仪的第一个未被分配的旗帜分配给他，也就是爆0，其中用蓝色的线表示该旗帜分配给滑稽1，则可得图。
紧接着按照上一步，把滑稽2喜欢的第一个未被分配的旗帜分配给他。这时发现滑稽1已经把爆0分配到了，那么此时采用和平原则，滑稽2退而分配AK-IOI，则可得图。
轮到滑稽3了，发觉：不好！AK-IOI被滑稽2拿走了！滑稽3不甘把AK-IOI的机会让给滑稽2，于是和滑稽2进行了深度沟通，于是滑稽2答应的换面旗帜。
滑稽2答应后发觉事情没这么简单，他唯一能换的旗帜被滑稽1拿走了。于是他只好去和滑稽1聊了聊。滑稽1于是好心的让出了爆0的旗帜，选择了溢出。其中橙色的线表示暂时撤销该分配关系。
于是滑稽2可以换上了爆0的旗帜
滑稽3开心的拿到了AK-IOI的旗帜
接下来留下了滑稽4，可是不论怎样让步也无法给他腾出他心仪的旗帜了（可以自己推导一下）。于是我们就得到了最终的分配情况。
算法实现
简单的DFS+循环。前置条件当然是得会写个简单的递归函数。1
2
3
4
5
6
7
8
9
10
11
12
13
14bool find(int x){
int i,j;
for (j=1;j<=m;j++){
//扫描每个flag
if(line[x][j]==true && used[j]==false){
used[j]=1;
if(girl[j]==0 || find(girl[j])){
girl[j]=x;
return true;
}
}
}
return false;
}
（持续更新中…）
