description

題目描述

小凸和小方是好朋友，小方給小凸一個 N×M（N≤M）的矩陣 A，要求小凸從其中選出 N 個數，其中任意兩個數字不能在同一行或同一列，現小凸想知道選出來的 N 個數中第 K大的數字的最小值是多少。

輸入格式
第一行給出三個整數 N、M、K。接下來 N 行，每行 M個數字，用來描述這個矩陣。
輸出格式
輸出選出來的 N個數中第 K大的數字的最小值。

樣例
Input
3 4 2
1 5 6 6
8 3 4 3
6 8 6 3
Output
3

數據范圍與提示
1≤K≤N≤M≤250,1≤Ai,j≤10^9

solution

第$K$大最小值，明顯套路往二分上面思考

不妨二分最后的答案

那么問題轉化為選擇邊的邊權不超過答案的情況下的最大匹配數$\ge n?k+1$

code

#include <cstdio> #include <cstring> #include <iostream> using namespace std; #define maxn 255 int n, m, k, l, r; bool vis[maxn]; int match[maxn]; int matrix[maxn][maxn];bool find( int x, int lim ) {for( int i = 1;i <= m;i ++ ) {if( ! vis[i] && matrix[x][i] <= lim ) {vis[i] = 1;if( ! match[i] || find( match[i], lim ) ) {match[i] = x;return 1;}}}return 0; }int check( int x ) {memset( match, 0, sizeof( match ) );int ans = 0;for( int i = 1;i <= n;i ++ ) {memset( vis, 0, sizeof( vis ) );if( find( i, x ) ) ans ++;}return ans; }int main() {scanf( "%d %d %d", &n, &m, &k );for( int i = 1;i <= n;i ++ )for( int j = 1;j <= m;j ++ ) {scanf( "%d", &matrix[i][j] );r = max( r, matrix[i][j] );}int ans;while( l <= r ) {int mid = ( l + r ) >> 1;if( check( mid ) >= n - k + 1 ) ans = mid, r = mid - 1;else l = mid + 1;}printf( "%d\n", ans );return 0; }

總結

以上是生活随笔為你收集整理的[SCOI2015]小凸玩矩阵 （匈牙利+二分）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。