题意：用p（500）个矩形（给出左下角和右上角）拼成一个n×m（30×30）的大矩形，输出最少使用个数。

把n×m每个格子都看成交叉十字循环双向链的一列，于是有n×m列，每个矩形都覆盖了一些列，于是就转化成01矩阵的精确覆盖，直接上模板。

建图的时候注意细节

#include<cstdio>
const int N=505005,INF=0x3f3f3f3f;
struct DLX
{
    int L[N],R[N],U[N],D[N],row[N],col[N];
    int H[505];
    int ansd,ans[505];
    int s[1005];
    int tot,n,m;
    void init(int _n,int _m)
    {
    	n=_n;  m=_m;
    	tot=m;
    	for (int i=0;i<=m;i++) L[i]=i-1,R[i]=i+1,U[i]=i,D[i]=i,s[i]=0;
    	L[0]=m;  R[m]=0;
    	for (int i=1;i<=n;i++) H[i]=-1;
    }
    void link(int i,int j)
    {
    	s[j]++;
    	++tot;
    	row[tot]=i;  col[tot]=j;

    	U[tot]=U[j];  D[tot]=j;  D[U[j]]=tot;	U[j]=tot;
    	if (H[i]<0)
		{
			H[i]=tot; L[tot]=tot; R[tot]=tot;
		}
		else
		{
			L[tot]=L[H[i]];  R[tot]=H[i]; R[L[H[i]]]=tot; L[H[i]]=tot;
		}
    }
    void remove(int c)
    {
        R[L[c]]=R[c];  L[R[c]]=L[c];
        for (int i=D[c];i!=c;i=D[i])
            for (int j=R[i];j!=i;j=R[j])
            {
            	s[col[j]]--;
                D[U[j]]=D[j];
                U[D[j]]=U[j];
            }
    }
    void resume(int c)
    {
    	R[L[c]]=c;	L[R[c]]=c;
        for (int i=U[c];i!=c;i=U[i])
            for (int j=L[i];j!=i;j=L[j])
            {
            	s[col[j]]++;
                D[U[j]]=j;
                U[D[j]]=j;
            }
    }
    void dfs(int d)
    {
    	if (d-1>=ansd) return ;
        if (R[0]==0)
        {
            if (d-1<ansd) ansd=d-1;
            return;
        }
        int c=R[0];
        for (int i=R[0];i!=0;i=R[i])
			if (s[i]<s[c]) c=i;
        remove(c);
        for (int i=D[c];i!=c;i=D[i])
        {
        	ans[d]=row[i];
            for (int j=R[i];j!=i;j=R[j]) remove(col[j]);
            dfs(d+1);
            for (int j=L[i];j!=i;j=L[j]) resume(col[j]);
        }
        resume(c);
        return;
    }
}g;
int main()
{
	int t;
	int n,m,p,sx,sy,ex,ey;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d%d",&n,&m,&p);
		g.init(p,n*m);
		for (int k=1;k<=p;k++)
		{
			scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
			for (int i=sx+1;i<=ex;i++)
				for (int j=sy+1;j<=ey;j++) g.link(k,(i-1)*m+j);
		}
		g.ansd=INF;
		g.dfs(1);
		if (g.ansd<INF) printf("%d\n",g.ansd);
		else printf("-1\n");
	}
}