我有以下代码是 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]
istrue
iff there is an edge from pigeoni
to holej
, 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
。这个图形算法是否正常工作或者我犯了一些错误?
最佳答案
要么是你的初始化错误,要么是 bpm()
中的条件错误:
if (graph[u][u])
graph
的对角线上没有设置为true
的元素,因此bpm()
总是完全失败。也不清楚为什么您需要单独测试对角线。也许应该是 if (graph[u][v])
,或者其他。
(您的缩进有些不尽如人意;将这样的 if
条件与 for
循环控件放在同一行是非常常规的做法。顺便提一下, matchL
和 matchR
的初始化仅适用于 2 的补码机器。)
关于c++ - 图中的二分匹配,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7937772/