题解 P4251 【[SCOI2015]小凸玩矩阵】
starseven
2020-05-08 20:49:28
[题面](https://www.luogu.com.cn/problem/P4251)
我们先看一道例题：
[P1129 [ZJOI2007]矩阵游戏](https://www.luogu.com.cn/problem/P1129)
这道例题是二分图的入门题当中的难题（对我来说），当时我在机房和以为同学讨论了一晚上才懂，哈哈哈。
#### 游戏的目标，即通过若干次操作，使得方阵的主对角线(左上角到右下角的连线)上的格子均为黑色。
我们一看，对角线均为黑色，好吧，我讲不清楚，但是你看了我讲的之后可以看看讲懂我的题解。
我们看得出来无论怎么交换都不会影响行和列的黑子有矛盾，就是重合，所有就将每行和每列连边，然后跑二分图匹配（说实在话，我觉得例题对于二分图的思维难度都比这道题高……）
现在给大家看看讲懂我的[博客](https://www.luogu.com.cn/blog/sswcdak/solution-p1129)
这个是[俾斯麦](https://www.luogu.com.cn/user/119937)（洛谷名）的，如有侵权，作者将及时删除。
现在我们看这道题
#### 其中任意两个数都不能在同一行或者同一列。
这就是裸题了啊！我们就直接每一次每行和每列连边，当然，因为我们要求答案，发现不能直接求出，所以考虑二分答案，因此我们连的边必须是小于等于我们二分出来的东西，因此我们就每次清零一次，就可以了。
现在贴代码
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
using namespace std;
const int MAXN = 255;
inline int rd(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)) {f=ch=='-'?0:1;ch=getchar();}
while(isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return f?x:-x;
}
int n,m,k,w[MAXN*MAXN];
int a[MAXN][MAXN],tot,ans,now;
int head[MAXN*MAXN],cnt;
int vis[MAXN*MAXN],num,match[MAXN*MAXN];
int to[MAXN*MAXN<<1],nxt[MAXN*MAXN<<1];
inline void add(int bg,int ed){
to[++cnt]=ed,nxt[cnt]=head[bg],head[bg]=cnt;
}
bool dfs(int x){
for(register int i=head[x];i;i=nxt[i]){
int u=to[i];
if(vis[u]!=num){
vis[u]=num;
if(!match[u] || dfs(match[u])){
match[u]=x;
return true;
}
}
}
return false;
}
inline bool check(int Mid){
memset(head,0,sizeof(head));
memset(match,0,sizeof(match));
ans=cnt=0;
for(register int i=1;i<=n;i++)
for(register int j=1;j<=m;j++)
if(a[i][j]<=Mid) add(i,j);
for(register int i=1;i<=n;i++){
num++;
if(dfs(i)) ans++;
}
if(ans>n-k) return true;
return false;
}
int main(){
n=rd(),m=rd(),k=rd();
for(register int i=1;i<=n;i++)
for(register int j=1;j<=m;j++){
a[i][j]=rd();
w[++tot]=a[i][j];
}
sort(w+1,w+1+tot);
int l=1,r=tot,mid;
while(l<=r){
mid=l+r>>1;
if(check(w[mid])) {
now=mid;
r=mid-1;
}
else l=mid+1;
}cout<<w[now]<<endl;
return 0;
}
```