HDU3335 – Divisibility(DLX)

传送门：HDU3335

【题意】给出n个整数，求一个最大的集合，使得集合中所有数互相不能整除(a%b != 0, b%a != 0)；

【分析】网上好多都是二分匹配。在斌神的DLX专题里看到的这题才想到用DLX来做，可是最终还是看了别人的题解才会的；可以以每个数分别建成行列01矩阵，i行j列表示j列能被i整除，则只要求出最大的行能覆盖满所有列即可；由于求可重复覆盖的DLX中会去掉同一列已有1的所有其他行的1，则正好把有冲突的数都去掉了，求出最大行就是最大的集合。

【AC CODE】15ms

#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 = 1000+10, M = MAXN*MAXN;
int lt[M],rt[M],up[M],down[M],col[M],tol,cnt[MAXN];
LL a[MAXN];

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);
}
int f()
{
	int ans = 0;
	for(int c = rt[0];c;c = rt[c]) ans++;
	return ans;
}
void remove(int 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)
{
	for(int i = up[c]; i != c; i = up[i])
		lt[rt[i]] = rt[lt[i]] = i, ++cnt[col[i]];
}
int mx;
void dfs(int d)
{
	if(d+f() <= mx) return;
	if(!rt[0])
	{
		if(mx < d) mx = 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])
	{
		remove(i);
		for(int j = rt[i]; j != i; j = rt[j]) remove(j);
		dfs(d+1);
		for(int j = lt[i]; j != i; j = lt[j]) reset(j);
		reset(i);
	}
}
int main()
{
#ifdef SHY
	freopen("d:\\1.txt", "r", stdin);
#endif
	int t;
	scanf("%d", &t);
	while(t--)
	{
		int n;
		scanf("%d", &n);
		repe(i,1,n) scanf("%I64d", &a[i]);
		init(n);
		repe(i,1,n)
		{
			int ft = tol;
			repe(j,1,n)
			{
				if(a[i]%a[j] == 0 || a[j]%a[i] == 0)
				{
					col[tol] = j;
					lt[tol] = tol-1,rt[tol] = tol+1,up[tol] = up[j], down[tol] = j;
					down[up[j]] = tol, up[j] = tol;
					cnt[j]++,tol++;
				}
			}
			if(ft != tol) lt[ft] = tol-1,rt[tol-1] = ft;
		}
		mx = 0;
		dfs(0);
		printf("%d\n",mx);
	}
	return 0;
}