「SCOI2015」小凸玩矩阵 解题报告

「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