hdu3498whosyourdaddy(DLX+A*解重复覆盖问题)
谨以此题，献给中秋夜还在默默刷题的孩纸们。。
题目请戳这里
题目大意：给n个点，m个关系(a,b)，表示点a和点b相邻。每个点最多4个相邻点。现在如果消灭某个点，就可以同时消灭与之相邻的点。现在问最少要消灭几个点，能使每个点都至少被消灭一次。
题目分析：最小点支配集的求解。NP难问题。好在数据规模不大，搜索可以解决。不过要用dancing links+A*优化。
重复覆盖和精确覆盖的区别仅仅是选中一列后只删除这一列即可，不用像精确覆盖那样先删掉所有覆盖这列的行，再删除这些行能覆盖的列保证每列只覆盖一次。
另外要加一个启发函数剪枝。关于这个剪枝函数，就是估计在当前局面下，最少还要几行才能覆盖所有剩下的列。因此这是一个估计上界。具体做法与精确覆盖的删除操作比较像。先选中未被删除的一列，删除覆盖该列的所有行，同时删除这些行覆盖的所有列。由此估计出覆盖剩余列需要的行数的上界。
详情请见代码：
#include <iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int N = 60;const int M = 360;const int inf = 0x3f3f3f3f;bool flag[N][N];int n,m,num,ans;int u[M],d[M],l[M],r[M],row[M],col[M],s[M],h[M];void init(){ memset(h,0,sizeof(h)); memset(s,0,sizeof(s)); int i; for(i = 0;i <= n;i ++) { u[i] = d[i] = i; r[i] = (i + 1) % (n + 1); l[i] = (i - 1 + n + 1) % (n + 1); } num = n + 1;}void build(int i,int j){ if(h[i]) { r[num] = h[i]; l[num] = l[h[i]]; r[l[num]] = num; l[r[num]] = num; } else { h[i] = num; l[num] = r[num] = num; } s[j] ++; u[num] = u[j]; d[num] = j; d[u[num]] = num; u[j] = num; col[num] = j; row[num] = i; num ++;}void remove(int x){ for(int i = d[x];i != x;i = d[i]) l[r[i]] = l[i],r[l[i]] = r[i],s[col[i]] --;}void resume(int x){ for(int i = u[x];i != x;i = u[i]) l[r[i]] = r[l[i]] = i,s[col[i]] ++;}int A(){ int ret = 0; int i,j,k; bool vis[N]; memset(vis,false,sizeof(vis)); for(i = r[0];i;i = r[i]) { if(vis[i] == false) { vis[i] = true; ret ++; for(j = d[i];j != i;j = d[j]) for(k = r[j];k != j;k = r[k]) vis[col[k]] = true; } } return ret;}void dfs(int dp){ if(dp + A() >= ans)//少个等号就TLE... return; int i,j; if(r[0] == 0) { ans = min(ans,dp); return; } int Max = inf; int maxcol; for(i = r[0];i;i = r[i]) { if(s[i] < Max) { Max = s[i]; maxcol = i; } } for(i = d[maxcol];i != maxcol;i = d[i]) { remove(i); for(j = r[i];j != i;j = r[j]) { remove(j); s[col[j]] --; } dfs(dp + 1); for(j = l[i];j != i;j = l[j]) { resume(j); s[col[j]] ++; } resume(i); }}int main(){ int i,j; while(scanf("%d",&n) != EOF) { scanf("%d",&m); memset(flag,false,sizeof(flag)); while(m --) { scanf("%d%d",&i,&j); flag[i][j] = true;//= flag[j][i] } init(); for(i = 1;i <= n;i ++) for(j = 1;j <= n;j ++) if(flag[i][j] || i == j)//i == j!!! build(i,j); ans = inf; dfs(0); printf("%d\n",ans); } return 0;}