#P3229. 矩阵匹配(200分)
-
1000ms
Tried: 57
Accepted: 15
Difficulty: 7
所属公司 :
华为od
矩阵匹配(200分)
思路:二分答案 + 二分图匹配
前置知识:
二分答案:如没学过,搞懂https://leetcode.cn/problems/koko-eating-bananas/
二分图匹配:如没学过,搞懂https://leetcode.cn/problems/broken-board-dominoes/
本题原题是:BZOJ 4443: [Scoi2015]小凸玩矩阵
思路:
考虑二分第k大的值。对于二分出来的mid,把矩阵中小于二分出来的答案的,行向列连边跑二分图匹配,看看匹配数是否大于n-k+1。
我们虽然保证了选出来的数一定是第K大的,那我们怎么保证一定有K-1个比这个数大的数能被选出来。由于我们选出来的是最小的第K大,那么如果他不能满足,比他大的肯定也不能满足
JavaScript
// 引入readline模块
const readline = require('readline');
// 创建readline接口实例
const rl = readline.createInterface({
input: process.stdin, // 设置输入流
output: process.stdout // 设置输出流
});
let n, m, K, mx; // 定义变量
let myMap = []; // 初始化二维数组
// 逐行读取输入
rl.on('line', (line) => {
if (!n) { // 如果n未定义
[n, m, K] = line.split(' ').map(Number); // 读取行数、列数和K值
mx = 0; // 初始化mx
} else {
const row = line.split(' ').map(Number);
myMap.push([0, ...row]);; // 读取二维数组数据
mx = Math.max(mx, ...row); // 更新mx
}
}).on('close', () => { // 读取完毕后执行
console.log(solve(mx)); // 输出结果
});
// 二分第k大的值的大小
function solve(mx) {
let l = 1, r = mx;
let ans = 0;
while (l <= r) {
const mid = Math.floor((l + r) / 2);
if (check(mid)) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
return ans;
}
// 将小于等于p的元素设为True,大于p的元素设为False,构建匹配图
function check(p) {
const mp = myMap.map(row => row.map(val => val <= p));
let ans = 0;
const match = new Array(m + 1).fill(0);
for (let i = 1; i <= n; i++) {
const chw = new Array(m + 1).fill(true);
if (findMuniu(i, mp, chw, match)) {
ans++;
}
}
return ans >= n - K + 1;
}
// 这里就是一个匈牙利匹配
function findMuniu(x, mp, chw, match) {
// 在匹配图中寻找增广路径
if (!mp[x] || mp[x].length !== m + 1) return false; // 检查mp[x]是否定义且长度正确
for (let j = 1; j <= m; j++) {
if (mp[x][j] && chw[j]) {
chw[j] = false;
if (match[j] === 0 || findMuniu(match[j], mp, chw, match)) {
match[j] = x;
return true;
}
}
}
return false;
}
Java
import java.util.Scanner;
import java.util.Vector;
public class Main {
static int n, m, K;
static Vector<Vector<Integer>> myMap;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
m = scanner.nextInt();
K = scanner.nextInt();
myMap = new Vector<>(n + 1);
// 初始化 myMap 并添加 m+1 个子向量
for (int i = 0; i <= n; i++) {
myMap.add(new Vector<>(m + 1));
for (int j = 0; j <= m; j++) {
myMap.get(i).add(0);
}
}
int mx = 0;
// 读取用户输入的数字并存储在 myMap 中
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
int num = scanner.nextInt();
myMap.get(i).set(j, num);
mx = Math.max(mx, myMap.get(i).get(j));
}
}
int result = solve(mx);
System.out.println(result);
}
// 找到一个点的 Muniu 匹配的方法
static boolean findMuniu(int x, Vector<Vector<Boolean>> mp, Vector<Boolean> chw, Vector<Integer> match) {
// 遍历 myMap 的列向量中的每个元素
for (int j = 1; j <= m; j++) {
// 如果 mp 和 chw 的相应位置为 true 且未匹配
if (mp.get(x).get(j) && chw.get(j)) {
// 将 chw 的相应位置设置为 false 并继续匹配
chw.set(j, false);
// 如果 match 的相应位置为 0 或者找到了一个新的匹配
if (match.get(j) == 0 || findMuniu(match.get(j), mp, chw, match)) {
// 将 match 的相应位置设置为 x 并返回 true
match.set(j, x);
return true;
}
}
}
return false;
}
// 检查给定整数 p 是否满足条件
static boolean check(int p) {
// 创建一个新的 Vector<Vector<Boolean>> 对象 mp
Vector<Vector<Boolean>> mp = new Vector<>(n + 1);
// 为 mp 的每个子向量添加 m+1 个子向量
for (int i = 0; i <= n; i++) {
mp.add(new Vector<>(m + 1));
for (int j = 0; j <= m; j++) {
mp.get(i).add(false);
}
}
// 遍历 myMap 的行向量中的每个元素
for (int i = 1; i <= n; i++) {
// 遍历 myMap 的列向量中的每个元素
for (int j = 1; j <= m; j++) {
// 如果 myMap 的行向量中的元素小于等于 p
mp.get(i).set(j, myMap.get(i).get(j) <= p);
}
}
// 创建一个新的 Vector<Integer> 对象 match
Vector<Integer> match = new Vector<>(m + 1);
for (int i = 0; i <= m; i++) {
match.add(0);
}
// 计算满足条件的匹配数
int ans = 0;
// 遍历 myMap 的列向量中的每个元素
for (int i = 1; i <= n; i++) {
// 创建一个新的 Vector<Boolean> 对象 chw
Vector<Boolean> chw = new Vector<>(m + 1);
for (int j = 0; j <= m; j++) {
chw.add(true);
}
// 使用 findMuniu 方法检查是否有一个满足条件的匹配
if (findMuniu(i, mp, chw, match)) {
ans++;
}
}
// 如果满足条件的匹配数达到或超过 n-K+1 则返回 true
return ans >= n - K + 1;
}
// 根据给定的最大值 mx 找到满足条件的整数 p 的值
static int solve(int mx) {
// 设置变量 l 和 r 的初始值
int l = 1, r = mx;
// 设置答案变量 ans 的初始值为 0
int ans = 0;
// 使用 while 循环在 l 和 r 之间进行二分查找
while (l <= r) {
// 计算中间值 mid
int mid = (l + r) / 2;
// 如果满足条件 check(mid) 则更新答案并将 r 设置为 mid-1
if (check(mid)) {
ans = mid;
r = mid - 1;
} else {
// 否则将 l 设置为 mid+1
l = mid + 1;
}
}
// 返回答案
return ans;
}
}
Python
def is_match_possible(p, mp, n, m, K):
# 构建匹配图
match_graph = [[mp[i][j] <= p for j in range(m + 1)] for i in range(n + 1)]
matching_count = 0
matching_result = [0] * (m + 1)
# 遍历每个元素以寻找增广路径
for i in range(1, n + 1):
visited = [True] * (m + 1)
if find_augmenting_path(i, match_graph, visited, matching_result, m):
matching_count += 1
# 检查匹配数是否大于等于 (n - K + 1)
return matching_count >= n - K + 1
def binary_search(mx, my_map, n, m, K):
left, right = 1, mx
result = 0
while left <= right:
mid = (left + right) // 2
if is_match_possible(mid, my_map, n, m, K):
result = mid
right = mid - 1
else:
left = mid + 1
return result
def find_augmenting_path(x, match_graph, visited, matching_result, m):
for j in range(1, m + 1):
if match_graph[x][j] and visited[j]:
visited[j] = False
if matching_result[j] == 0 or find_augmenting_path(matching_result[j], match_graph, visited, matching_result, m):
matching_result[j] = x
return True
return False
def main():
mx = 0
n, m, K = map(int, input().split())
my_map = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
row = list(map(int, input().split()))
for j in range(1, m + 1):
my_map[i][j] = row[j - 1]
mx = max(mx, my_map[i][j])
print(binary_search(mx, my_map, n, m, K))
if __name__ == "__main__":
main()
C++
#include <iostream>
#include <vector>
using namespace std;
int n, m, K; // 声明变量 n, m, K,分别表示行数、列数和第K大元素的数量
vector<vector<int>> myMap; // 声明二维向量 myMap,用于存储输入的数字
// findMuniu 函数:实现匈牙利匹配算法,用于在矩阵中找到一个增广路径
bool findMuniu(int x, vector<vector<bool>>& mp, vector<bool>& chw, vector<int>& match) {
for (int j = 1; j <= m; j++) {
if (mp[x][j] && chw[j]) {
chw[j] = false;
if (match[j] == 0 || findMuniu(match[j], mp, chw, match)) {
match[j] = x;
return true;
}
}
}
return false;
}
// check 函数:检查给定的数字 p 是否可以添加到匹配图中
bool check(int p) {
vector<vector<bool>> mp(n + 1, vector<bool>(m + 1, false)); // 声明二维向量 mp,用于存储匹配图
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
mp[i][j] = (myMap[i][j] <= p); // 构建匹配图
}
}
int ans = 0;
vector<int> match(m + 1, 0); // 声明一维向量 match,用于存储匹配的数字
for (int i = 1; i <= n; i++) {
vector<bool> chw(m + 1, true); // 声明一维向量 chw,表示当前可用的数字
if (findMuniu(i, mp, chw, match)) {
ans++;
}
}
return ans >= n - K + 1; // 返回匹配数是否大于等于 n - K + 1
}
// solve 函数:使用二分查找算法找到矩阵中可以选出 M!/N! 种组合数组中第 K 大的数字的最小值
int solve(int mx) {
int l = 1, r = mx;
int ans = 0;
while (l <= r) {
int mid = (l + r) / 2;
if (check(mid)) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
return ans;
}
// 主函数
int main() {
cin >> n >> m >> K; // 输入 n, m, K 的值
myMap.resize(n + 1, vector<int>(m + 1, 0)); // 调整 myMap 的大小
int mx = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> myMap[i][j]; // 输入矩阵中的数字
mx = max(mx, myMap[i][j]); // 计算矩阵中的最大值
}
}
int result = solve(mx); // 调用 solve 函数
cout << result << endl; // 输出结果
return 0;
}
题目描述
从一个N∗M(N≤M)的矩阵中选出N个数,任意两个数字不能在同一行或同一列,求选出来的N个数中第K大的数字的最小值是多少
输入描述
输入矩阵要求:1≤K≤N≤M≤150
输入格式
N M K
N*M矩阵
输出描述
N∗M的矩阵中可以选出N!M!种组合数组,每个组合数组中第K大的数中的最小值。无需考虑重复数字,直接取字典排序结果即可
样例1
输入
3 4 2
1 5 6 6
8 3 4 3
6 8 6 3
输出
3
说明:N*M的矩阵中可以选出M!/N!种组合数组,每个组合数组中第K大的数中的最小值;上述输入中选出的数组组合为为1,3,6;1,3,3;1,4,8;1,4,3;…
上述输入样例中选出的组合数组有24种,最小数组为1,3,3,则2大的最小值为3
注意:结果是第K大的数字的最小值