鹰潭手机网站建设,厦门网站设计定制,陕西网站建设美化,北京专业网站制作description
题目描述
小凸和小方是好朋友#xff0c;小方给小凸一个 NM#xff08;N≤M#xff09;的矩阵 A#xff0c;要求小凸从其中选出 N 个数#xff0c;其中任意两个数字不能在同一行或同一列#xff0c;现小凸想知道选出来的 N 个数中第 K大的数字的最小值是多…description
题目描述
小凸和小方是好朋友小方给小凸一个 N×MN≤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
第KKK大最小值明显套路往二分上面思考
不妨二分最后的答案
那么问题转化为选择边的边权不超过答案的情况下的最大匹配数≥n−k1\ge n -k1≥n−k1
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;
}
