BEECROWD 2035题代码错误求助：输出与预期不符

阿根廷U18和U21橄榄球队各有N名球员，需共用N件T恤。T恤需满足两队使用时，每位球员的T恤前缀（可空）搭配唯一编号合法，目标是最大化所有T恤的前缀总长度。

我编写了如下C语言代码，当使用udebug提供的测试输入时，预期输出为25，但代码输出39，请求指出错误原因。

#include <stdio.h>
#include <string.h>

int main() {

    while(1)
    {
        int jogadores;
        scanf("%d", &jogadores);
        if(jogadores == -1)
        {
            break;
        }
        char sub18[jogadores][101];
        char sub21[jogadores][101];

        for(int i = 0; i < jogadores; i++)
        {
            scanf("%s", sub18[i]);
        }

        for(int i = 0; i < jogadores; i++)
        {
            scanf("%s", sub21[i]);
        }

        int letras_total = 0;

        for(int i = 0; i < jogadores; i++)
        {
            int letras = 0;
            for(int j = 0; j < jogadores; j++)
            {
                int k = 0;
                while(sub18[i][k] != '\0' && sub18[i][k] == sub21[j][k])
                {
                    k+=1;
                }
                if(k > letras)
                {
                    letras = k;
                }
            }
            letras_total += letras;
        }

        printf("%d\n", letras_total);
    }

    return 0;
}

测试输入 #

11
BABBABAABAABBAABABBBBAABABBAAAABABBBBBBBAAAABAA ABB BBBBBABAABAABBAABBAAABBABBBBABBBBBBBBBAABAAAABABABAABAABBBABBBAABABBAAAABBAABABBABABBBAB BABBAAABBBBABAAAABBBBBBBABAAAAABBABBAAAAAABBAABAAABABBBBAAAAABAABAAABBABBABAABA BABBBBBBBABBBAAAABBAAABABABABBAAAAABBAABAABABABAABABBABAAAABBBBBAB BBBBAAABBBBA BBBB ABBABBABABAAAAABAABABBABABBBBBAABABAABBAAABABBAABAAABBBAAABBABBBBAAABAAABAAABB BAABAABAAAAAABBABBAAABABBABAABBBABABABABBBABAAAABABBBAAAABBABAABBBBBABAAAABABABBABBB ABBBBAAABABABABBAABBAAABBBAABABBAABABABABBBABBABABA ABBBAABBBABBAAABAABBBABAAAAAAAAAAAABBAAAABBBABBBBBAAAAABAABA
BBABABBBAABABBAABBBBAABBAAABABAB BABAAABBBAAABABBABBBBAAAAABBAAABAAAABBBAABAABBBAABAABA AAAAAAAAAAABBAABBBBABBABABBAAABAABBBBBBABBABBABAABABBAABBBAAAABBABAAABABABBABBBABAAAABBAAB BAAAAAABAABBABBABAAAAAAABAABBBBAABABAAAAAABABABBAABABBABAAAABAABAABBAABBAABABABAAABBAABBA BABBAAAAAAAAABABBBAABBBBAAABBABABAABABBBBABAABAABBABBBAAAAAABBABABBBABB AABABBABBABBBBABABBABABABBABABBBAAAAABBBBBBABBAAABAAABAAAAAABBBABABBBBABABBBBBBABABBABAAABABB BBABBAAABBAAABBBBABBBBBAAABABABAAABBABBBBBBABAAABABAAABAABABAAAABABAABABAAABA AABBBBABBAAABBABABABABABBBABBAABBBBABBBBBABBA AABABAAAABBABBAAAA AABBBBBBBBBBAAABBBABBBAABBBBBBBAABBBBBBABBB ABBABABABAABBBBBBABABBBABABA

预期输出：25，代码输出：39

错误原因分析 #

你的代码完全误解了问题的核心约束：

题目本质是要求给U18和U21的球员建立一一对应的完美匹配——每件T恤对应一对U18和U21球员，T恤的前缀必须是这对球员名字的公共前缀，我们需要让所有配对的最长公共前缀长度之和最大。

但你当前的逻辑是：对每个U18球员，找出和所有U21球员的最长公共前缀的最大值，直接把这些最大值相加。这相当于允许同一个U21球员被多个U18球员重复配对，完全违反了“每个U21球员只能对应一件T恤（即一个U18球员）”的规则。这种重复计算自然会让总和被高估，这就是测试用例中你得到39、远大于正确答案25的原因。

举个简单例子：假设U18有2个球员A、AA，U21有2个球员AA、AAA。你的代码会给A算最大公共前缀长度2（对应U21的AA），给AA算最大公共前缀长度3（对应U21的AAA），总和5。但实际完美匹配只能是A→AAA+AA→AA（总和1+2=3），或者A→AA+AA→AAA（总和2+2=4），都远小于你计算的结果。

修正思路 #

你需要把问题转化为二分图最大权完美匹配问题：

1. 构建二分图：左节点是U18的所有球员，右节点是U21的所有球员。
2. 给每条连接U18球员i和U21球员j的边赋予权值——即两个名字的最长公共前缀长度。
3. 求解这个二分图的最大权完美匹配，匹配的权值总和就是正确答案。

可以用KM算法实现二分图最大权匹配，该算法适合处理这类N规模不大的问题（比如测试用例的N=11）。

内容的提问来源于stack exchange，提问作者user27342045