2

我有以下代码，它是 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和目的如下。

给定一个表示为 m×n 矩阵的二分图，其中当当且graph[i][j]仅当从鸽子到洞true存在一条边时，计算可以找到洞的最大鸽子数量（每只鸽子一个）和最佳分配。ij

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

  • main()对所有鸽子进行循环，i并在每次迭代中

    • 清除seen[]所有0组件
    • calls bpm(i) and increments the maxflow counter
    • bpm(i) returns true iff pigeon i can be assigned a hole

  • cnt contains the number of happy pigeons.

In my case, cnt's value is output as 0. Does this graph algorithm work correctly or have I made some error?

4

1 回答 1

2

Either your initialization is faulty or this condition in bpm() is faulty:

       if (graph[u][u])

There is no element of graph on the diagonal which is set true, so bpm() always fails completely. It is also not clear why you'd be needing to test the diagonal alone. Maybe it should be if (graph[u][v]), or maybe something else.

(Your indentation leaves somewhat to be desired; it is extremely aconventional to put an if condition such as this on the same line as a for loop control. Incidentally, the initialization of matchL and matchR only works on 2's-complement machines.)

于 2011-11-27T03:44:32.923 回答