SCOI2015 小凸玩矩阵

wjh15101051's space

卧薪尝胆，厚积薄发。

SCOI2015 小凸玩矩阵

Date: Thu Nov 15 21:15:42 CST 2018

In Category: NoCategory

Description：

给一个 $N\times M$ 的矩阵 $A$ ，从其中选出 $N$ 个数，任意两个数字不能在同一行或同一列，求选出来的 $N$ 个数中第 $K$ 大的数字的最小值是多少。

$1\leqslant n\leqslant 250$

Solution：

先二分一个值，表示最终的答案小于等于这个数是否可行，然后把所有小于等于这个数的格子在行和列之间连边，判断最大匹配是否够 $N-K+1$ 个即可。

Code：


#include

#include

#include

#include

#include

#include

#include

using namespace std;

int n,m,x;

#define MAXN 252

int a[MAXN][MAXN];

struct edge

{

	int to,nxt;

}e[MAXN * MAXN];

int edgenum = 0;

int lin[MAXN];

void add(int a,int b)

{

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	return;

}

int match[MAXN];

bool v[MAXN];

bool find(int k)

{

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(!v[e[i].to])

		{

			v[e[i].to] = true;

			if(match[e[i].to] == -1 || find(match[e[i].to]))

			{

				match[e[i].to] = k;

				return true;

			}

		}

	}

	return false;

}

bool check(int w)

{

	memset(lin,0,sizeof(lin));

	edgenum = 0;

	for(int i = 1;i <= n;++i)

		for(int j = 1;j <= m;++j)

			if(a[i][j] <= w)add(i,j);

	int ans = 0;

	memset(match,-1,sizeof(match));

	for(int i = 1;i <= n;++i)

	{

		memset(v,false,sizeof(v));

		if(find(i))++ans;

	}

	return (ans >= n - x + 1);

}

int main()

{

	scanf("%d%d%d",&n,&m,&x);

	for(int i = 1;i <= n;++i)

		for(int j = 1;j <= m;++j)

			scanf("%d",&a[i][j]);

	int l = 1,r = 1000000000,mid;

	while(l < r)

	{

		mid = ((l + r) >> 1);

		if(check(mid))r = mid;

		else l = mid + 1;

	}

	cout << l << endl;

	return 0;

}

In tag: 图论-匈牙利算法算法-二分

wjh15101051