C++中的二部分匹配，我的代碼有什麼問題？

Question

我曾參與過雙邊匹配問題，而且我顯然遇到了麻煩來解決它。

讓我告訴你是什麼問題。

作爲輸入形式，它給了我N，M這是工作中的人數和工作中不同種類的工作的數量。 在下面的N行中，它告訴我們，它告訴我們人們可以做多少種工作。在下面的數字中，他們會告訴我們哪些工作可以ith人能夠做到。作業si的數量將滿足1 < = si < = M。 那麼，如果每個人一次只能工作一個或更少的工作，那麼最多可以完成多少工作？

這是問題，我希望這對你有意義;）我道歉我的英語不好。回到這一點，這是我的代碼。

#include <stdio.h> 

int n, m, dfscheck[1003], check[1003], input[1003][1003], back[1003], tmp, count=0; 

void dfs(int num) 
{ 
    int i, j; 
    if(check[num]==0) 
    { 
     tmp=-1; 
     check[num]=1; 
     return; 
    } 
    if(dfscheck[num]==1) 
     return; 
    dfscheck[num]=1; 
    for(j=1; j<=input[back[num]][0]; j++) 
    { 
     dfs(input[back[num]][j]); 
     if(tmp==-1) 
     { 
      back[input[back[num]][j]]=back[num]; 
      return; 
     } 
    } 
} 

int main(void) 
{ 
    int i, j, flag ,k; 
    scanf("%d %d", &n, &m); 
    for(i=1; i<=n; i++) 
    { 
     scanf("%d", &input[i][0]); 
     for(j=1; j<=input[i][0]; j++) 
      scanf("%d", &input[i][j]); 
    } 
    for(i=1; i<=n; i++) 
    { 
     flag=0; 
     for(j=1; j<=input[i][0]; j++) 
      if(check[input[i][j]]==0) 
      { 
       check[input[i][j]]=1; 
       count++; 
       flag=1; 
       back[input[i][j]]=i; 
       break; 
      } 

     if(flag==0) 
      for(j=1; j<=input[i][0]; j++) 
      { 
       for(k=0; k<=1001; k++) 
        dfscheck[k]=0; 
       tmp=0; 
       dfs(input[i][j]); 
       if(tmp==-1) 
       { 
        back[input[i][j]]=i; 
        count++; 
       } 
      } 
    } 
    printf("%d", count); 
    return 0; 
} 

tmp的名字真的很難理解代碼，所以... tmp在函數dfs中像標誌一樣工作。它告訴它是否找到了匹配。

我得到了錯誤的答案，既沒有運行時錯誤，也沒有超過時間。我已經閱讀了其他人編寫的幾種不同的代碼，並且我無法找到代碼中的哪個部分是錯誤的。

我發現我的代碼與其他人的代碼不同，我沒有定義數組A [i]，顯示哪個工作與第i個人匹配，與我的代碼中的Back數組完全相反。據我瞭解他們的代碼，其目的是在我們進入dfs之前發現第i個人已經匹配。我認爲這種情況不會發生。由於沒有流從第i個人的節點流出，流是不可能從作業節點轉到最大流中的節點的。

我想說我的想法，即使它是無用的，以防它可以幫助你給我一些建議。無論如何，讓我有你的意見！ 非常感謝你的時間。

Answer 1

一兩件事，看起來怪怪的：

  if(tmp==-1) 
      { 
       back[input[i][j]]=i; 
       count++; 
       // I would expect to see "break;" here 
      } 

，如果你找到一個方法來分配的人，我給你增加計數工作，再進行嘗試，看看是否能找到一種替代辦法分配同一個人。這意味着你可能最終將同一個人分配給多個工作！

我建議插入一個「break」聲明一旦你找到了一份工作的人。