hdu6749.Mosquito（hall定理）

http://acm.hdu.edu.cn/showproblem.php?pid=6749

hall定理：二分图有完美匹配当且仅当对于左侧的任意集合S所连向的集合大小>=|S|

对于本题就直接二分答案，nm处理2^K枚举判断即可

code

#include <bits/stdc++.h>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define abs(x) ((x)>0?(x):-(x))
#define low(x) ((x)&-(x))
#define ll long long
//#define file
using namespace std;

int a[7][3],f[64],T,n,m,K,i,j,k,l,L,R,Mid;
const int p[7]={1,2,4,8,16,32,64};

bool pd(int t)
{
	int i,j,k,l;
	
	memset(f,0,sizeof(f));
	fo(i,1,n)
	{
		fo(j,1,m)
		{
			l=0;
			fo(k,1,K)
			if (abs(i-a[k][0])+abs(j-a[k][1])<=t)
			l|=p[k-1];
			++f[l];
		}
	}
	fo(i,1,p[K]-1) f[i]+=f[i-low(i)];
	fo(i,0,p[K]-1)
	{
		fo(j,1,K)
		if (i&p[j-1])
		f[i]-=a[j][2];
		if (f[i]>0)
		return 0;
	}
	return 1;
}

int main()
{
	#ifdef file
	freopen("g.in","r",stdin);
	#endif
	
	scanf("%d",&T);
	for (;T;--T)
	{
		scanf("%d%d%d",&n,&m,&K);k=0;
		fo(i,1,K) scanf("%d%d%d",&a[i][0],&a[i][1],&a[i][2]),k+=a[i][2];
		if (k<n*m) {printf("-1
");continue;};
		
		L=0;R=n*m;
		while (L<R)
		{
			Mid=(L+R)/2;
			if (!pd(Mid)) L=Mid+1; else R=Mid;
		}
		printf("%d
",L);
	}
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}