传送门FZU1686
【分析】和精确覆盖大致一样,只是删除的时候不需要删除选择行所覆盖的所有点的其他行,只要删除选中行覆盖的所有列即可,需要加上A*启发函数f()来强力剪枝,否则时间巨慢
【AC CODE】46ms
#include <cstdio> #include <cstring> #include <cctype> #include <cmath> #include <set> //#include <unordered_set> #include <queue> #include <stack> #include <vector> #include <string> #include <algorithm> using namespace std; typedef long long LL; #define rep(i,a,n) for(int i = a; i < n; i++) #define repe(i,a,n) for(int i = a; i <= n; i++) #define per(i,n,a) for(int i = n; i >= a; i--) #define clc(a,b) memset(a,b,sizeof(a)) const int INF = 0x3f3f3f3f, MAXN = 15*15+10, M = MAXN*MAXN; /*和精确覆盖大致一样,只是删除的时候不需要删除选择行所覆盖的所有点的其他行,只要删除选中行覆盖的所有列即可 在找最小情况时,需要加上A*启发函数f()来强力剪枝,否则时间巨慢*/ struct DLX { private: int lt[M],rt[M],up[M],down[M],row[M],col[M],tol; int cnt[MAXN]; void remove(int c)//删除列c所有元素 { for(int i = down[c]; i != c; i = down[i]) lt[rt[i]] = lt[i],rt[lt[i]] = rt[i],--cnt[col[i]]; } void reset(int c)//恢复列c { for(int i = up[c]; i != c; i = up[i]) lt[rt[i]] = rt[lt[i]] = i,++cnt[col[i]]; } bool vis[MAXN]; int f()//最少还需要几行才能覆盖 { int ret = 0; for(int c = rt[0];c;c = rt[c]) vis[c] = true; for(int c = rt[0];c;c = rt[c]) { if(vis[c]) { ret++; vis[c] = false; for(int i = down[c]; i != c; i = down[i]) for(int j = rt[i]; j != i; j = rt[j]) vis[col[j]] = false; } } return ret; } public: void init(int maxc) { repe(i,0,maxc) lt[i] = i-1,rt[i] = i+1,up[i] = down[i] = i; lt[0] = maxc,rt[maxc] = 0; tol = maxc+1; clc(cnt,0); } void add_row(int r,int len, int *a) { if(!len) return; int ft = tol; rep(i,0,len) { int c = a[i]; row[tol] = r,col[tol] = c; lt[tol] = tol-1,rt[tol] = tol+1,up[tol] = up[c],down[tol] = c; down[up[c]] = tol, up[c] = tol; cnt[c]++,tol++; } lt[ft] = tol-1,rt[tol-1] = ft; } int mi; void dance(int d) { if(d+f() >= mi) return;//估价剪枝 if(0 == rt[0]) { if(mi > d) mi = d; return; } int c = rt[0]; for(int i = rt[0];i;i = rt[i]) if(cnt[c] > cnt[i]) c = i; for(int i = down[c];i != c; i = down[i])//选择行row[i],并删除他所能覆盖的所有列 { remove(i); for(int j = rt[i]; j != i; j = rt[j]) remove(j);//删除行row[i]能覆盖的所有列 dance(d+1); for(int j = lt[i]; j != i; j = lt[j]) reset(j); reset(i); } } }dlx; int a[20][20],tmp[MAXN],num[20][20]; int main() { #ifdef SHY freopen("d:\\1.txt", "r", stdin); #endif int n,m; while(~scanf("%d %d", &n, &m)) { int sum = 0; rep(i,0,n) { rep(j,0,m) { scanf("%d", &a[i][j]); if(a[i][j]) num[i][j] = ++sum; } } dlx.init(sum); int n1,m1,id = 0; scanf("%d %d",&n1, &m1); repe(i,0,n-n1) { repe(j,0,m-m1) { int ei = i+n1-1,ej = j+m1-1; int len = 0; repe(ii,i,ei) { repe(jj,j,ej) { if(a[ii][jj]) tmp[len++] = num[ii][jj]; } } dlx.add_row(++id,len,tmp); } } dlx.mi = INF; dlx.dance(0); printf("%d\n", dlx.mi); } return 0; }