学步园

如果a[i]%a[j]==0,建边i—>j,二分匹配求出最小路径覆盖ans，被一条路径覆盖的点最多只能选一个，所以最多能选ans个。

这题用最大独立集更容易理解，选n个点，任意两点之间没有关系，就是最大独立集。。

#include<stdio.h>
#include<string.h>
bool map[1001][1001],link[1001];
int match[1001];
int n;
__int64 a[1001];
int find(int u)
{
	int i;
	for(i=0;i<n;i++)
	{
		if(!link[i]&&map[u][i])
		{
			link[i]=true;
			if(match[i]==-1||find(match[i])==1)
			{
				match[i]=u;
				return 1;
			}
		}
	}
	return 0;
}
int main()
{
	int i,j,t,sum;
	scanf("%d",&t);
	while(t--)
	{
		memset(map,false,sizeof(map));
		scanf("%d",&n);
		for(i=0;i<n;i++)
		{
			scanf("%I64d",&a[i]);
			for(j=0;j<i;j++)
			{
				if(a[i]%a[j]==0||a[j]%a[i]==0)
					map[j][i]=true;
			}
		}
		sum=0;
		memset(match,-1,sizeof(match));
		for(i=0;i<n;i++)
		{
			memset(link,false,sizeof(link));
			sum+=find(i);
		}
		printf("%d\n",n-sum);
	}
	return 0;
}