C++ 中的二分匹配，我的代码有什么问题？

Question

我研究过一个二分匹配问题，显然我解决起来很麻烦。

让我告诉你问题是什么。

作为输入表格，它给了我N，M，这是工作中的人数和工作中不同类型工作的数量。在接下来的 N 行中，它告诉我们 s 告诉我们 it 人可以做多少种工作。在后面的数字中，他们会告诉我们，这个人可以做什么工作。作业数量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个人的节点流出，所以流量不可能从作业的节点到最大流量的节点。

虽然没用，但还是想说说自己的想法，希望能帮到大家，给我一些建议。无论如何，让我发表你的意见！！！非常感谢您的宝贵时间。

Answer 1

一件看起来很奇怪的事情是：

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

如果您找到一种方法将第 i 个人分配给某项工作，您会增加计数，然后继续尝试查看是否可以找到另一种方法来分配同一个人。这意味着您最终可能会将同一个人分配给多个工作！

我建议您在为该人找到工作后插入 "break;" 声明。

C++ 中的二分匹配，我的代码有什么问题？

bipartite matching in C++, what is wrong in my code?

algorithm

bipartite

max-flow