飞行员配对问题 | 网络流：最大二分匹配（匈牙利算法）

野性酷女 2023-02-14 01:44 19阅读 0赞

> ## 飞行员配对问题 ##
> 
> <table> 
>  <tbody> 
>   <tr> 
>    <td>成绩</td> 
>    <td>10</td> 
>    <td>开启时间</td> 
>    <td>2020年04月21日 星期二 10:10</td> 
>   </tr> 
>   <tr> 
>    <td>折扣</td> 
>    <td>0.8</td> 
>    <td>折扣时间</td> 
>    <td>2020年05月30日 星期六 23:55</td> 
>   </tr> 
>   <tr> 
>    <td>允许迟交</td> 
>    <td>否</td> 
>    <td>关闭时间</td> 
>    <td>2020年05月30日 星期六 23:55</td> 
>   </tr> 
>  </tbody> 
> </table>
> 
> 问题描述: 第二次世界大战时期, 英国皇家空军从沦陷国征募了大量外籍飞行员. 由皇家空军派出的每一架飞机都需要配备在航行技能和语言上能互相配合的2名飞行员, 其中一名是英国飞行员, 另一名是外籍飞行员, 在众多的飞行员中, 每一名外籍飞行员都可以与其他若干名英国飞行员很好地配合. 如何选择配对的飞行员才能使一次派出最多的飞机.
> 
> 算法设计: 对于给定的外籍飞行员与英国飞行员的配合情况, 找出皇家空军能派出最多的飞行员数.
> 
> 数据输入: 第1行有2个正整数m和n. n是皇家空军的飞行员总数(n<100); m是外籍飞行员数. 外籍飞行员编号1~m, 英国飞行员编号m+1~n. 接下来每行2个整数i和j, 表示外籍飞行员i可以与英国飞行员j配合. 最后以2个-1结束.
> 
> 结果输出: 皇家空军能派出最多的飞行员数.
> 
> <table> 
>  <thead> 
>   <tr> 
>    <th>&nbsp;</th> 
>    <th>测试输入</th> 
>    <th>期待的输出</th> 
>    <th>时间限制</th> 
>    <th>内存限制</th> 
>    <th>额外进程</th> 
>   </tr> 
>  </thead> 
>  <tbody> 
>   <tr> 
>    <td>测试用例 1</td> 
>    <td><a href="http://lexue.bit.edu.cn/mod/programming/testcase/download_io.php?id=162188&amp;test=124365&amp;type=in&amp;download=0" rel="nofollow">以文本方式显示</a> 
>     <ol> 
>      <li>5&nbsp;10↵</li> 
>      <li>1&nbsp;7↵</li> 
>      <li>1&nbsp;8↵</li> 
>      <li>2&nbsp;6↵</li> 
>      <li>2&nbsp;9↵</li> 
>      <li>2&nbsp;10↵</li> 
>      <li>3&nbsp;7↵</li> 
>      <li>3&nbsp;8↵</li> 
>      <li>4&nbsp;7↵</li> 
>      <li>4&nbsp;8↵</li> 
>      <li>5&nbsp;10↵</li> 
>      <li>-1&nbsp;-1&nbsp;↵</li> 
>     </ol></td> 
>    <td><a href="http://lexue.bit.edu.cn/mod/programming/testcase/download_io.php?id=162188&amp;test=124365&amp;type=out&amp;download=0" rel="nofollow">以文本方式显示</a> 
>     <ol> 
>      <li>4↵</li> 
>     </ol></td> 
>    <td>1秒</td> 
>    <td>64M</td> 
>    <td>0</td> 
>   </tr> 
>  </tbody> 
> </table>

--------------------

这是一个**二分图的匹配问题**，可以转化为最大流的算法取求解，也可以直接使用**匈牙利算法。**本文直接使用匈牙利算法实现。

关于算法的原理与过程理解可以看看这一篇文章：[匈牙利算法（简单易懂）][Link 1]。匈牙利算法还是简单易懂的，本质上就是贪心。下面直接粘上匈牙利算法的AC代码，配合友好的注释应该很好懂啦~

//匈牙利算法解决二部图的最大流问题
    
    #include <cstdio>
    #include <cstring>
    
    #define MAXN 105
    
    int m, n;   //二部图左侧有m个，总计有n个
    bool connected[MAXN][MAXN];   //图的连接关系
    int pre[MAXN] = {0};   //next[j]=i:左侧的 i 点与右侧的 j 点匹配
    
    /* 处理输入与初始化 */
    void Init() {
        scanf("%d %d", &m, &n);
        int i, j;
        while (true) {
            scanf("%d %d", &i, &j);
            if (i == -1 && j == -1)
                break;
            connected[i][j] = true;
        }
    }
    
    bool vis[MAXN];
    
    /* 寻找左侧的点与右侧匹配 */
    bool Find(int left) {
        //依次遍历右部顶点
        for (int right = m + 1; right <= n; right++) {
            //寻找 相邻 且 此次查找没有被考虑过 的右侧点
            if (connected[left][right] && !vis[right]) {
                vis[right] = true;
                //寻找 没有匹配 或 该点的匹配点可以另有匹配 的右侧点
                if(pre[right] == 0 || Find(pre[right])) {
                    pre[right] = left;   //匹配
                    return true;
                }
            }
        }
        return false;
    }
    
    int CalcAns(){
        int ans = 0;
        /* 讨论每一个左部顶点 */
        for(int left = 1; left <= m; left++) {
            memset(vis, false, sizeof(vis));   //每次寻找前需要初始化
            if(Find(left))  //如果能找到
                ans++;  //匹配数字加一
        }
        return ans;
    }
    
    int main() {
        Init();
        printf("%d\n", CalcAns());
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70][]

[Link 1]: https://blog.csdn.net/sunny_hun/article/details/80627351?ops_request_misc=&request_id=&biz_id=102&utm_term=%E5%8C%88%E7%89%99%E5%88%A9%E7%AE%97%E6%B3%95%E2%80%98&utm_medium=distribute.pc_search_result.none-task-blog-2~blog~sobaiduweb~default-1-80627351
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200530162405717.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw==,size_16,color_FFFFFF,t_70