「SCOI2015」小凸玩矩阵

我好沙茶啊

把点当边连接行和列,在外面二分答案跑图的匹配就行了

我最开始二分方向搞反了,样例没过。

脑袋一抽,这绝壁要费用流,连忙打了个KM

然后wa了,一想这个不是完备匹配啊,k个鬼的m

又换回二分图匹配...


Code:

#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
#define koito_yuu 1
using std::min;
using std::max;
const int N=252;
template <class T>
void read(T &x)
{
x=0;char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) x=x*10+c-'0',c=getchar();
}
int n,m,k,a[N][N],g[N][N],mat[N],vis[N],bee[N*N];
bool dfs(int now)
{
for(int i=1;i<=m;i++)
if(g[now][i]&&!vis[i])
{
vis[i]=1;
if(!mat[i]||dfs(mat[i]))
return mat[i]=now,true;
}
return false;
}
bool check(int x)
{
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) g[i][j]=a[i][j]<=x;
int sum=0;
memset(mat,0,sizeof mat);
for(int i=1;i<=n;i++)
{
memset(vis,0,sizeof vis);
sum+=dfs(i);
}
return sum>=k;
}
int main()
{
read(n),read(m),read(k);k=n-k+1;
int l=1,r=0;
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) read(a[i][j]),bee[++r]=a[i][j];
std::sort(bee+1,bee+1+r);
r=std::unique(bee+1,bee+1+r)-bee-1;
while(l<r)
{
int mid=l+r>>1;
if(check(bee[mid])) r=mid;
else l=mid+1;
}
printf("%d\n",bee[l]);
return 0;
}

2019.2.27

05-08 15:47