标签：head int 矩阵 len edge 100001 小凸 SCOI2015
[SCOI2015]小凸玩矩阵
链接:https://www.luogu.com.cn/problem/P4251
题解:可以发现去掉了$k$的限制之后,原问题是一个二分图的最大独立集的问题,加上了$k$的限制就可以直接二分,但要注意的是求第$k$大的,所以要转化为求第$n-k+1$小的。
```
#include
using namespace std;
struct node
{
int v,data,nxt;
};
node edge[100001];
int n,m,head[100001],matched[100001],len,k,ans;
bool used[100001];
void add(int x,int y,int z)
{
edge[++len].v=y;
edge[len].data=z;
edge[len].nxt=head[x];
head[x]=len;
return;
}
bool dfs(int x,int L)
{
for (int i=head[x];i>0;i=edge[i].nxt)
if (!used[edge[i].v]&&edge[i].data<=L)
{
used[edge[i].v]=1;
if (matched[edge[i].v]==0||dfs(matched[edge[i].v],L))
{
matched[edge[i].v]=x;
return 1;
}
}
return 0;
}
bool check(int L)
{
ans=0;
for (int i=1;i<=m;++i)
matched[i]=0;
for (int i=1;i<=n;++i)
{
for (int j=1;j<=m;++j)
used[j]=0;
ans+=dfs(i,L);
}
return ans>=k;
}
int main()
{
int d,res=1e9;
cin>>n>>m>>k;
k=n+1-k;
for (int i=1;i<=n;++i)
for (int j=1;j<=m;++j)
{
cin>>d;
add(i,j,d);
}
int first=1,last=1e9,mid;
while (first<=last)
{
mid=(first+last)/2;
if (check(mid))
{
last=mid-1;
res=min(res,mid);
}
else
first=mid+1;
}
cout<
标签：head,
int,
矩阵,
len,
edge,
100001,
小凸,
SCOI2015
From： https://www.cnblogs.com/zhouhuanyi/p/16983469.html