【日常学习】【二分图匹配】【匈牙利算法】codevs4265 大智的妹子们题解

灰太狼 2022-08-09 14:57 61阅读 0赞

题目描述 Description

有一天，在动漫社的大智给妹子们买了Love Live!的cosplay服，刚好⑨件。

恰好有⑨个闻讯而来的妹子们，她们都拿到了自己想要的衣服。然后她们拍了各种照片，发到了朋友圈里，于是越来越多的妹子知道了这件事，都来请求大智买cosplay服。

于是大智又买了m种cosplay服（每种只有一件），吸引来了n个妹子，但是这些妹子喜欢的衣服不同，有人喜欢南小鸟的，又有人喜欢矢泽妮可的，还有的妹子喜欢多个角色。

大智把妹子们的需求记录了下来，发现总共有p对。但是妹子太多，大智很乱，于是有些妹子的需求没有记，有些妹子的需求又记重复了。

大智想尽可能的满足妹子的需求来当一个好人，于是他来求你。

输入描述 Input Description

第一行有三个正整数：n、m、p。

接下来p行，每行有2个正整数a和b，代表第a号妹子想要b号cosplay服。

输出描述 Output Description

只有一行，输出可以满足的最大需求数。

样例输入 Sample Input

9 9 10

1 2

2 3

3 4

3 5

3 4

5 1

6 8

7 7

9 2

8 9

样例输出 Sample Output

数据范围及提示 Data Size & Hint

对于30%的数据：n，m <= 9；p <= 20。

对于70%的数据：n，m <= 200；p <= 400。

对于90%的数据：n，m <= 1000；p <= 2000。

对于100%的数据：n，m <= 5000；p <= 10000。

裸的二分图匹配

学习资料：[http://www.renfei.org/blog/bipartite-matching.html][http_www.renfei.org_blog_bipartite-matching.html] 在此感谢宋任飞老师的博文 给了我很多启发

具体参见博文即可，我们先放上本题代码，然后再对于一些上述博文中没有提及的部分做简单的补充说明

//codevs4265 大智的妹子们 二分图匹配-递归匈牙利
    //copyright by ametake
    //Hungarian cheer up!匈牙利人加油！布拉迪斯拉发加油！
    #include
       
        
    #include
        
         
    #include
         
          
    using namespace std;
    
    const int maxn=10000+10;
    struct node
    {
        int t,nxt;
    }e[maxn*2];
    int hd[maxn],et=0;
    int n,m,p;
    int matching[maxn],check[maxn];
    
    void add(int x,int y)
    {
        et++;
        e[et].t=y;
        e[et].nxt=hd[x];
        hd[x]=et;
    }
    
    bool dfs(int u)
    {
        for (int i=hd[u];i;i=e[i].nxt)
        {
            int v=e[i].t;
            if (!check[v])
            {
                check[v]=true;
                if (matching[v]==-1||dfs(matching[v]))
                {
                    matching[v]=u;
                    matching[u]=v;
                    return true;
                }
            }
        }
        return false;
    }
    
    int hungarian()
    {
        int ans=0;
        memset(matching,-1,sizeof(matching));
        for (int i=1;i<=n+m;i++)
        {
            if (matching[i]==-1)
            {
                memset(check,false,sizeof(check));
                if (dfs(i)) ++ans;
            }
        }
        return ans;
    }
    
    int main()
    {
        scanf("%d%d%d",&n,&m,&p);
        int x,y;
        for (int i=1;i<=p;i++)
        {
            scanf("%d%d",&x,&y);
            add(x,y+n);
            add(y+n,x);
        }
        printf("%d\n",hungarian());
        return 0;
    }

由于NOIP临近，只学了递归版，且递归两种方法只学习了一种。因此这里只介绍这种递归版本。

所谓匈牙利算法，其实就是：找一个未匹配点，从这个点找交替路，直到找到一个未匹配点。这时由于交替路的两头均是非匹配边，这条路上非匹配边比匹配便多一条，于是我们可以让所有的匹配边变为非匹配边，非匹配边变成匹配边，这样又多了一条匹配边。所以增广路算法的作用是：改进匹配，增加一条匹配边。如果无法找到增广路，那么意味着已经达到最大匹配。

在递归算法的实现上，我们依次扫每一个左集合中的点，如果未匹配就从这个点找增广路，最终得到的就是最大匹配。

为什么这样最终得到的是最大匹配呢？请看代码：

bool dfs(int u)
    {
        for (int i=hd[u];i;i=e[i].nxt)//找到一条增广路（找到非匹配点）就退出，否则一直循环枚举所有可能路径
        {
            int v=e[i].t;
            if (!check[v])
            {
                check[v]=true;
                if (matching[v]==-1||dfs(matching[v]))//如果找到未匹配点那么搜索完成，改变匹配边；否则继续从下个节点的匹配点找增广路
                {
                    matching[v]=u;
                    matching[u]=v;
                    return true;
                }
            }
        }
        return false;
    }

由于我们循环枚举了所有可能路径，对于每个点，我们尽量使它有匹配，这条路没有匹配就从下一条路找。最大匹配，实际上就是让匹配点数尽量多，因此当我们从没一个当前无匹配的点尝试增加匹配，最终得到的是最大匹配。

实际上，在处理二分图匹配问题时，**边可以加单向边，扫点也可以只扫两个区间中的一个区间即可，check标记其实也并非路径上所有点都为true**。（其实这些似乎并不重要）

为什么可以加单向边？

请注意，上述dfs程序中，当我们扩展u的边找到一条边指向v时，如果v是匹配点，我们执行的操作是：

dfs(matching[v]);

我们搜索的是v这个点的匹配点，而不是v。这意味着，我们每次搜索时搜索的总是左边集合里的点，因此可以加单向边。

为什么扫点可以只扫一个区间？

因为所有的边必然是从一个区间通向另一个的，如果左边的区间已经尽量匹配，那么右边每次扫时由于扫到的点已经匹配，一定会立刻退出，不扫也罢。

为什么check标记的路径上并非所有的点都是true？

请注意，正如同上面搜索只搜了左边区间的点，我们check也只对右边区间的点标记true即可。因为由于只可能由左边集合搜索，当没有其他边可以搜索，返回时，必然是返回到右边集合，此时之前搜过的右集合的点已经是true了，就会退出。

那么我也稍微提一下另一种dfs，我们称之为第二方案。

这种方法和我们的方法唯二的区别在于：增广路更新匹配只写

matching[v]=u;

且下面搜索时并不判断这个点是否已经被匹配，一律搜索。

为什么可以这么写呢？因为在这种情况下， 我们只标记右边集合里的点的匹配点是谁，左边集合是没有匹配点的。

借用显摆同志的话来说，如果我们写

matching[v]=u;
                    matching[u]=v;

相当于是把左边的点给“打死”了，这样，当我们扫右边时，左边已经被确定了匹配，无法继续搜索。而第二方案扫右边时左边仍然是未匹配，因此可以继续搜索，搜出的结果除以二是正确结果。如果只扫左边，第二方案也是正确的，因为即使左边未标记，右边也是标记的，会直接退出，时间复杂度并不会高。

最后引入几个定理：

**定理1：最大匹配数 = 最小点覆盖数（这是 Konig 定理）**

为什么呢？最大匹配数的每条边都被他的一个顶点覆盖，因此最小点覆盖数大于等于最大匹配数。那么为什么是等于？假设还有一条边没有被匹配点覆盖，那么这条边连接的必然是两个未匹配点，于是又构成了一个新的匹配，最大匹配就不成立了。因此，最大匹配数等于最小点覆盖数。

我在之前曾写过一篇树的最小点覆盖的题解，那道题用树形DP做的，也可以用二分图来做。树本身就是二分图，把树的第一层放在左集合，那么第二层在右集合，第三层在左集合，以此类推，符合二分图的定义。我们在每两个点之间连双向边，跑最大匹配，如果用第二种方案跑出来要除以二，第一种方案也就是我们的代码不必除以二。

然而二分图复杂度为O(VE)，而树形DP为O(V)，更优。  
  
  
**定理2：定点数 = 最大匹配数 + 最大独立集数**  
  
独立集，指的是在图中选出最多的点，使他们没有边相连。每个匹配边选一个点，除此之外的点必然独立。  
  
**定理3：最小路径覆盖数 = 顶点数 - 最大匹配数 = 最大独立集数**

针对DAG=有向无环图，不证明了（我懒）= =

终于结束了啊···

今天的古诗文是沈括《梦溪笔谈·象数一》中的文字，宋史中有记载，历史课本也有提到。沈括一直是我非常崇敬的人。博闻强识，文理俱佳，怡然自得，实在令我憧憬。

——月本无光，犹银丸，日耀之乃光耳。

[http_www.renfei.org_blog_bipartite-matching.html]: http://www.renfei.org/blog/bipartite-matching.html