华为OD机试 - 矩阵匹配（Java & JS & Python & C & C++）

03-20 阅读 0评论

题目描述

从一个 N * M（N ≤ M）的矩阵中选出 N 个数，任意两个数字不能在同一行或同一列，求选出来的 N 个数中第 K 大的数字的最小值是多少。

$华为OD机试 - 矩阵匹配（Java & JS & Python & C & C++）,华为OD机试 - 矩阵匹配（Java & JS & Python & C & C++）,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,使用,我们,Python,第1张$

（图片来源网络，侵删）

输入描述

输入矩阵要求：1 ≤ K ≤ N ≤ M ≤ 150

输入格式：

N M K

N*M矩阵

输出描述

N*M 的矩阵中可以选出 M! / N! 种组合数组，每个组合数组种第 K 大的数中的最小值。无需考虑重复数字，直接取字典排序结果即可。

备注

注意：结果是第 K 大的数字的最小值

（图片来源网络，侵删）

用例

输入

3 4 2

1 5 6 6

8 3 4 3

6 8 6 3

输出

说明

N*M的矩阵中可以选出 M！/ N！种组合数组，每个组合数组种第 K 大的数中的最小值；

上述输入中选出数组组合为：

1,3,6;

1,3,3;

（图片来源网络，侵删）

1,4,8;

1,4,3;

......

上述输入样例中选出的组合数组有24种，最小数组为1,3,3，则第2大的最小值为3

题目解析

本题需要我们从矩阵中选取N个元素，这个N元素的特点是：任意两个不能同行同列。

而满足上面条件的N个元素存在多组，我们需要找到着各个组中第K大元素的最小值。

难点一：如何从矩阵中找到N个互相不同行同列的元素呢？

暴力枚举的话，肯定会超时，因此需要寻找更优解法。

根据要求，每行每列只能有一个元素被选择，即可以认为每个行号只能和一个列号进行配对，且配对过的列号不能再和其他行号配对，而形成了配对关系的行号，列号，其实就是一个元素的坐标位置。

因此，找N个互相不同行同列的元素，其实就是在二分图（所有行号一部分，所有列号一部分）找N个边的匹配。

如下图所示

关于二分图的知识可以看下：

HDU - 2063 过山车（Java & JS & Python & C）-CSDN博客

看完上面博客后，我们就可以继续后面说明了。

现在我们已经有了二分图了，也就可以找到具有N个边的"匹配"，但是这种"匹配"可能非常多，难道要全部找出来，然后对比每个"匹配"中第K大，那不还是暴力吗？

题目需要我们多组N个元素中的第K大元素的最小取值，

换位思考一下，假设我们已经知道了第K大的最小取值是kth，那么：

检查矩阵中是否至多找到（N - K + 1 个） ≤ kth 的元素值，且这些元素值互不同行同列
N个数中，有K-1个数比kth大，那么相对应的有 (N - (K-1)) = (N - K + 1 ) 个数 ≤ kth。

即找的 N - K + 1 个数中包含了 kth（第K大值）本身。

而kth的大小和二分图最大匹配是正相关的，因为：

每个匹配边其实就是行号到列号的配对连线

而行号和列号的组合其实就是坐标位置，根据坐标位置可以得到一个矩阵元素值

因此kth越小，意味着可以找到的 ≤ kth 的矩阵元素越少，相反的，kth 越大，则找到的 ≤ kth 的矩阵元素越多。

因此kth值大小和二分图最大匹配数是线性关系，我们可以使用二分法，来枚举kth。

二分枚举的范围是：1 ~ 矩阵元素最大值，这里不用担心二分枚举到kth不是矩阵元素，因为这种情况会被过滤掉，原因是：我们要找 N - K + 1 个 = N-K+1 个，则说明当前kth取大了，我们应该尝试更小的kth值，即缩小二分右边界为kth-1

如果kth使得二分图最大匹配当二分左右边界重合时的kth值即为题解。

关于二分法，可以看下：

算法设计 - 二分法和三分法，洛谷P3382_二分法与三分法-CSDN博客

JS算法源码

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
 
void (async function () {
  const [n, m, k] = (await readline()).split(" ").map(Number);
 
  let min = 1;
  let max = -Infinity;
 
  const matrix = [];
  for (let i = 0; i  1;
 
    // 检查mid作为N个数中第K大值时，是否存在N-K+1个= n - k + 1;
  }
 
  function dfs(i, kth, match, vis) {
    // 行号 i 发起了配对请求
 
    // 遍历每一个列号j
    for (let j = 0; j = n - k + 1;
  }
  public static boolean dfs(int i, int kth, int[] match, boolean[] vis) {
    // 行号 i 发起了配对请求
    // 遍历每一个列号j
    for (int j = 0; j  n >> m >> k;
    int low = 1;
    int high = INT_MIN;
    for (int i = 0; i > matrix[i][j];
            high = max(high, matrix[i][j]);
        }
    }
    // 二分枚举第K大值
    while (low > 1;
        // 检查mid作为N个数中第K大值时，是否存在N-K+1个不大于它的值
        if (check(mid)) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    cout