最小路徑覆蓋，覆蓋的點都不選，剩余的點就沒有關系可以選上
[cpp]
#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;
}
#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;
}
