「SCOI2015」小凸玩矩阵
2024-09-03 11:57:39
问题分析
题目给了充足的暗示,我们只需要二分答案然后跑匈牙利即可。要相信匈牙利的速度
参考程序
#include <bits/stdc++.h>
using namespace std;
const int Maxn = 310;
const int INF = 2147483647;
int N, M, K, A[ Maxn ][ Maxn ], Max, Min;
int Map[ Maxn ][ Maxn ], Vis[ Maxn ], Mx[ Maxn ], My[ Maxn ];
int Dfs( int x ) {
for( int i = 1; i <= M; ++i ) {
if( Map[ x ][ i ] == 0 ) continue;
if( Vis[ i ] ) continue;
Vis[ i ] = 1;
if( My[ i ] == 0 || Dfs( My[ i ] ) ) {
Mx[ x ] = i; My[ i ] = x;
return 1;
}
}
return 0;
}
bool Check( int Mid ) {
memset( Map, 0, sizeof( Map ) );
memset( Mx, 0, sizeof( Mx ) );
memset( My, 0, sizeof( My ) );
for( int i = 1; i <= N; ++i )
for( int j = 1; j <= M; ++j )
if( A[ i ][ j ] <= Mid ) Map[ i ][ j ] = 1;
int Ans = 0;
for( int i = 1; i <= N; ++i ) {
memset( Vis, 0, sizeof( Vis ) );
Ans += Dfs( i );
}
return Ans >= ( N - K + 1 );
}
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", &A[ i ][ j ] );
Max = 0, Min = INF;
for( int i = 1; i <= N; ++i )
for( int j = 1; j <= M; ++j )
Max = max( A[ i ][ j ], Max ), Min = min( A[ i ][ j ], Min );
int Ans = 0;
while( Max >= Min ) {
int Mid = ( Max + Min ) >> 1;
if( Check( Mid ) ) Ans = Mid, Max = Mid - 1; else Min = Mid + 1;
}
printf( "%d\n", Ans );
return 0;
}
最新文章
- 浅谈WebLogic和Tomcat
- IOS 绘图教程Quartz2D
- poj 3262 Protecting the Flowers
- JavaScript继承
- Apache 日志管理,获取客户端端口号
- LVS ip-tun服务器脚本
- mongodb(二) 安装和使用
- SQL SERVER 服务启动后停止,某些服务由其它服务或程序使用时将自动停止
- sublime返回上一编辑位置
- oracl使用DataBase Configuration Assistant创建、删除数据库
- HTML (1)href与Action,get post
- (转).net开发者对android开发一周的学习体会
- JQuery中回车键登陆
- codeforces 782B The Meeting Place Cannot Be Changed (三分)
- Centos7-卸载自带的jdk 安装jdk8
- 《An Introduction to Signal Smoothing》译文
- Socket实现聊天客户端
- Leetcode中sort排序遇到的一些问题
- 收藏一个带动画效果的ScrollViewer以及ScrollBar的模板
- Python 扫盲