bzoj 4443 小凸玩矩阵

Posted on | Views:

二分答案 + 二分图最大匹配.

二分答案 $mid$ ,权值 $\le mid$ 的边才有用,第 $k$ 大就是第 $n-k+1$ 小,判断一下最大匹配数是否达到 $n-k+1$ ,达到则合法,否则不合法.

时间复杂度 $O(n^3\cdot \log (\max v))$ .

匈牙利算法每次 $dfs$ 前都需要清空 $vis$ 数组.

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int inf=1e9;
const int MAXN=256;
int a[MAXN][MAXN];
vector<int> E[MAXN<<1];
int pr[MAXN<<1],vis[MAXN<<1];
int n,m,k;
bool dfs(int u)
{
	int t=E[u].size();
	for(int i=0;i<t;++i)
	{
		int v=E[u][i];
		if(!vis[v])
		{
			vis[v]=1;
			if(!pr[v] || dfs(pr[v]))
			{
				pr[v]=u;
				pr[u]=v;
				return true;
			}
		}
	}
	return false;
}
bool check(int mid)
{
	for(int i=1;i<=n+m;++i)
		E[i].clear();
	memset(pr,0,sizeof pr);
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			if(a[i][j]<=mid)
			{
				E[i].push_back(j+n);
				E[j+n].push_back(j);
			}
	int ans=0;
	for(int i=1;i<=n;++i)
		if(!pr[i])
		{
			memset(vis,0,sizeof vis);
			ans+=(int)(dfs(i));
		}	
	return ans>=(n+1-k);
}
int main()
{
	n=read(),m=read(),k=read();
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			a[i][j]=read();
	int L=1,R=inf,ans=inf;
	while(L<=R)
	{
		int mid=(L+R)>>1;
		if(check(mid))
			ans=mid,R=mid-1;
		else
			L=mid+1;
	}
	cout<<ans<<endl;
	return 0;
}