温州网站制作设计,做网站要什么资质,网站建设 前景 html5,app软件设计公司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;
}
