gpt4 book ai didi

algorithm - C++ 中的二分匹配,我的代码有什么问题?

转载 作者:塔克拉玛干 更新时间:2023-11-03 05:16:14 25 4
gpt4 key购买 nike

我曾处理过一个二分匹配问题,显然我很难解决它。

让我告诉你问题出在哪里。

作为输入表格,它给了我 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个人的节点流出,所以流量不可能从作业的节点到最大流量的节点。

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

最佳答案

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

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

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

我建议插入一个“break;”为该人找到工作后的声明。

关于algorithm - C++ 中的二分匹配,我的代码有什么问题?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/45694253/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com