摘要:二分图矩阵行列建模

[SCOI2015]小凸玩矩阵

题面

题目分析

每行每列只能选一个,可以想到二分图的套路:将行和列连边.

这样来跑二分图匹配,就可以保证一行对应一边.

因为要求出最小的第k大值,于是想到二分出一个第k大的数,然后小于这个数的就行向列建边,跑出二分图最大匹配.

如果最大匹配大于n-k,就说明这个数字还可以变得再小,缩小二分的边界.

我的代码写出来常数比较大.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include "iostream"
#include "cstdio"
#include "cstring"
#include "cmath"
#include "cstdlib"
#include "cctype"
#include "iomanip"
#include "algorithm"
#include "set"
#include "queue"
#include "map"
#include "stack"
#include "deque"
#include "vector"
#include "time.h"
#define lxl long long
#define R register
#define INF 0x3f3f3f3f
#define debug(x) printf("debug:%lld\n",x)
const lxl maxn=255;
lxl n,m,k,l=1,r=1000000000,mid,ans,EdgeSize;
lxl a[maxn][maxn],match[maxn*maxn<<1],head[maxn*maxn<<1],flag[maxn*maxn<<1];
struct _Edge
{
lxl next,to;
}e[maxn*maxn<<2];
inline lxl read()
{
char c=getchar();
lxl f=1,x=0;
for(;!isdigit(c);c=getchar())(c=='-')&&(f=-1);
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
return f*x;
}
inline void EdgeAdd(lxl from,lxl to)
{
e[EdgeSize].to=to;
e[EdgeSize].next=head[from];
head[from]=EdgeSize++;
}
inline bool find(lxl now)
{
for(R int i(head[now]),to;~i;i=e[i].next)
{
to=e[i].to;
if(flag[to])continue;
flag[to]=true;
if(!match[to]||find(match[to]))
{
match[to]=now;
return true;
}
}
return false;
}
inline lxl Hungery()
{
lxl cnt=0;
for(R int i(1);i<=n;++i)
{
memset(flag,false,sizeof flag);
if(find(i))++cnt;
}
return cnt;
}
inline void build(lxl limit)
{
EdgeSize=0;
memset(head,-1,sizeof head),memset(match,0,sizeof match),memset(e,0,sizeof e);
for(R int i(1);i<=n;++i)
for(R int j(1);j<=m;++j)
if(a[i][j]<=limit)EdgeAdd(i,j+n);
}
inline bool check()
{
return Hungery()>n-k;
}
int main(void)
{
n=read(),m=read(),k=read();
for(R int i(1);i<=n;++i)
for(R int j(1);j<=m;++j)
a[i][j]=read();
while(l<=r)
{
mid=(l+r)>>1;
build(mid);
if(check())r=mid-1,ans=mid;
else l=mid+1;
}
printf("%lld\n",ans);
return 0;
}