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 列の行列として表される 2 部グラフを指定すると、graph[i][j]はtruepigeoniから hole へのエッジがある場合にj、穴を見つけることができる鳩の最大数 (鳩ごとに 1 つ) と最適な割り当てを計算します。

  • 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ます。このグラフ アルゴリズムは正しく機能しますか、それともエラーが発生しましたか?

4

1 に答える 1

2

初期化に問題があるか、次の状態にbpm()問題があります:

       if (graph[u][u])

graphset である対角線上の要素がないtrueため、bpm()常に完全に失敗します。対角線のみをテストする必要がある理由も明確ではありません。多分それはif (graph[u][v])、または多分何か他のものであるべきです。

(あなたのインデントは、いくらか望ましいものではありません。このような条件をループ制御ifと同じ行に置くことは非常に慣習的ではありません。ちなみに、 andの初期化は2 の補数マシンでのみ機能します。)formatchLmatchR

于 2011-11-27T03:44:32.923 に答える