最新华为OD机试真题-矩阵匹配问题(200分)

🍭 大家好这里是清隆学长 ，一枚热爱算法的程序员

💻 ACM金牌🏅️团队 ｜ 编程一对一辅导

✨ 本系列打算持续跟新华为OD-D卷的三语言AC题解

👏 感谢大家的订阅➕ 和 喜欢💗 和手里的小花花🌸

最新华为OD机试D卷目录，全、新、准，题目覆盖率达 95% 以上，支持题目在线评测

最新华为OD机试目录: https://www.nowcoder.com/discuss/636153620743897088?sourceSSR=users

📎 在线评测链接

矩阵匹配问题(200分)

🌍 评测功能需要 =>订阅专栏<= 后联系清隆解锁～

🍓OJ题目截图

📞 矩阵匹配问题

问题描述

给定一个 的矩阵，从中选出 个数，要求任意两个数字不能在同一行或同一列。求选出来的 个数中第 大的数字的最小值。

输入格式

第一行包含三个正整数 ，分别表示矩阵的行数、列数和要求的第 大的数字。

接下来 行，每行包含 个整数，表示矩阵的元素。

输出格式

输出一个整数，表示选出的 个数中第 大的数字的最小值。

样例输入

3 4 2
1 5 6 6
8 3 4 3
6 8 6 3

样例输出

3

样例解释

在给定的 矩阵中，可以选出 种组合数组。每个组合数组中第 大的数中的最小值为 。

数据范围

• 
• 矩阵中的元素为正整数

题解

题目要求从矩阵中选出 个数，使得任意两个数字不能在同一行或同一列，并且这些数中第 大的数的最小值最小。可以使用二分查找和匈牙利算法来解决这个问题。

具体步骤

1. 二分查找：我们需要找到一个数 ，使得矩阵中所有小于等于 的数可以构成一个满足条件的组合。为了找到这个 ，我们可以使用二分查找。
2. 匈牙利算法：在每次二分查找的过程中，我们需要判断当前的 是否可以满足条件。这里我们使用匈牙利算法来进行二分图的最大匹配。匈牙利算法是一种用于解决二分图最大匹配问题的算法。

参考代码

• Python

def find_match(x, mp, visited, match):
    for j in range(1, m + 1):
        if mp[x][j] and visited[j]:
            visited[j] = False
            if match[j] == 0 or find_match(match[j], mp, visited, match):
                match[j] = x
                return True
    return False

def check(p):
    mp = [[False] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            mp[i][j] = (matrix[i][j] <= p)
    
    ans = 0
    match = [0] * (m + 1)
    for i in range(1, n + 1):
        visited = [True] * (m + 1)
        if find_match(i, mp, visited, match):
            ans += 1
    
    return ans >= n - k + 1

def solve(mx):
    l, r = 1, mx
    ans = 0
    while l <= r:
        mid = (l + r) // 2
        if check(mid):
            ans = mid
            r = mid - 1
        else:
            l = mid + 1
    return ans

n, m, k = map(int, input().split())
matrix = [[0] * (m + 1) for _ in range(n + 1)]
mx = 0

for i in range(1, n + 1):
    row = list(map(int, input().split()))
    for j in range(1, m + 1):
        matrix[i][j] = row[j - 1]
        mx = max(mx, matrix[i][j])

result = solve(mx)
print(result)

• Java

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    static int n, m, k;
    static int[][] matrix;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        k = sc.next