c++ - 图中的二分匹配

Question

我有以下代码是 BPM 的实现(二分匹配，来自图论)

#include <iostream>
#include <cstring>
using  namespace std;
#define M 128
#define N 128
bool graph[M][N];
bool seen[N];
int matchL[M],matchR[N];
int n=4;
int m=4;

bool bpm(int u){

    for(int v=0;v<n;v++) if(graph[u][u])
    {
                if (seen[v]) continue;
                seen[v]=true;
                if(matchR[v] <0 || bpm(matchR[v])){
                    matchL[u]=v;
                    matchR[v]=u;
                    return true;
                }
    }

    return false;

}

int main(){

    graph[0][1]=1;
    graph[0][3]=1;
    graph[1][3]=1;
    graph[0][2]=1;
     memset(matchL,-1,sizeof(matchL));
     memset(matchR,-1,sizeof(matchR));
     int cnt=0;
     // memset(seen,0,sizeof(seen));
     for(int i=0;i<m;i++){

        memset(seen,0,sizeof(seen));
          if(bpm(i)) cnt++;

     }
     cout<<cnt<<endl;
    return 0;
}

cnt的定义和这段代码的用途如下。

Given a bipartite graph represented as an m-by-n matrix, where graph[i][j] is true iff there is an edge from pigeon i to hole j, computes the maximum number of pigeons that can find a hole (one per pigeon) and an optimal assignment.

• graph[m][n]、matchL[n]、matchR[m] 和 seen[m] 是全局数组。
• main() 将所有组件中的 matchL[] 和 matchR[] 初始化为 -1。

• main() 对所有鸽子 i 和每次迭代进行循环

  • 将所有组件中的seen[]清除为0
  • 调用 bpm(i) 并增加 maxflow 计数器
  • bpm(i) 返回 true 当且仅当鸽子 i 可以分配一个洞

• cnt 包含快乐鸽子的数量。

在我的例子中，cnt 的值输出为 0。这个图形算法是否正常工作或者我犯了一些错误？

Answer 1

要么是你的初始化错误，要么是 bpm() 中的条件错误:

       if (graph[u][u])

graph 的对角线上没有设置为true 的元素，因此bpm() 总是完全失败。也不清楚为什么您需要单独测试对角线。也许应该是 if (graph[u][v])，或者其他。

(您的缩进有些不尽如人意；将这样的 if 条件与 for 循环控件放在同一行是非常常规的做法。顺便提一下， matchL 和 matchR 的初始化仅适用于 2 的补码机器。)