最大匹配BPM模版（LRJ）

Wiking__acm

于 2013-03-19 13:02:37 发布

阅读量1k

点赞数

分类专栏：图论

本文链接：https://blog.csdn.net/Wiking__acm/article/details/8691198

版权

图论专栏收录该内容

114 篇文章

订阅专栏

本文介绍了一种基于邻接矩阵实现的二分图最大基数匹配算法，通过递归搜索来寻找增广路径，实现左部节点与右部节点间的最大匹配。详细展示了算法结构、初始化、匹配过程及求解最大匹配数的方法。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

const int maxn = 500 + 5; // 单侧顶点的最大数目

// 二分图最大基数匹配，邻接矩阵写法
struct BPM {
  int n, m;               // 左右顶点个数
  int G[maxn][maxn];      // 邻接表
  int left[maxn];         // left[i]为右边第i个点的匹配点编号，-1表示不存在
  bool T[maxn];           // T[i]为右边第i个点是否已标记

  void init(int n, int m) {
    this->n = n;
    this->m = m;
    memset(G, 0, sizeof(G));
  }

  bool match(int u){
    for(int v = 0; v < m; v++) if(G[u][v] && !T[v]) {
      T[v] = true;
      if (left[v] == -1 || match(left[v])){
        left[v] = u;
        return true;
      }
    }
    return false;
  }

  // 求最大匹配
  int solve() {
    memset(left, -1, sizeof(left));
    int ans = 0;
    for(int u = 0; u < n; u++) { // 从左边结点u开始增广
      memset(T, 0, sizeof(T));
      if(match(u)) ans++;
    }
    return ans;
  }

};

BPM solver;

时间复杂度邻接矩阵：最坏为O(n^3) 邻接表：O(mn) 。图中点的编号从0开始。