hihocoder #1122 二分图二•二分图最大匹配之匈牙利算法（*【模板】应用）

梳理整个算法：

1. 依次枚举每一个点i；
2. 若点i尚未匹配，则以此点为起点查询一次交错路径。

最后即可得到最大匹配数。

在这个基础上仍然有两个可以优化的地方：

1.对于点的枚举：当我们枚举了所有A中的点后，无需再枚举B中的点，就已经得到了最大匹配。
2.
在查询交错路径的过程中，有可能出现Ai与Bj直接相连，其中Bj为已经匹配的点，且Bj之后找不到交错路径。之后又通过Ai查找到了一条交错路径
{Ai,Bx,Ay,…,Az,Bj}延伸到Bj。由于之前已经计算过Bj没有交错路径，若此时再计算一次就有了额外的冗余。所以我们需要枚举每个Ai时
记录B集合中的点是否已经查询过，起点不同时需要清空记录。

伪代码：

Function FindPath(u)

    For v∈u的相邻节点

       标记v已经查询过

       If v未匹配 or FindPath(v的匹配的点) Then

            更改u的匹配为v

            Return Ture

        End If

    End For

Return False

For i ∈ V

    清空标记

   FindPath(i)

End If

输入

第1行：2个正整数，N,M(N表示点数 2≤N≤1,000，M表示边数1≤M≤5,000)
第2..M+1行：每行两个整数u,v，表示一条无向边(u,v)

输出

第1行：1个整数，表示最大匹配数

样例输入

样例输出

2

代码：

 #include <stdio.h>

 #include <string.h>

 #include <stdlib.h>

 #include <math.h>

 #include <algorithm>

 #define N 1001

 using namespace std;

 int n, m;

 int map[N][N];

 int link[N];

 bool vis[N];

 int dfs(int dd)

 {

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

     {

         if(vis[i]==false && map[dd][i]== )

         {

             vis[i]=true;

             if(link[i]==- || dfs(link[i]) )

             {

                 link[i]=dd;

                 return ;

             }

         }

     }

     return ;

 }

 int main()

 {

     scanf("%d %d", &n, &m);

     int i, j;

     int u, v;

     memset(map, , sizeof(map));

     memset(link, -, sizeof(link));

     for(i=; i<m; i++)

     {

         scanf("%d %d", &u, &v);

         map[u][v]=;

         map[v][u]=;

     }

     int cnt=;

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

     {

         memset(vis, false, sizeof(vis));

         cnt+=dfs(i);

     }

     printf("%d\n", cnt/ );

     return ;

 }

巴特西

hihocoder #1122 二分图二•二分图最大匹配之匈牙利算法（*【模板】应用）

输入

输出

最新文章

热门文章

巴特西

hihocoder #1122 二分图二•二分图最大匹配之匈牙利算法（*【模板】应用 ）

输入

输出

最新文章

热门文章

hihocoder #1122 二分图二•二分图最大匹配之匈牙利算法（*【模板】应用）