最小路径覆盖，覆盖的点都不选，剩余的点就没有关系可以选上
[cpp]
#include
#include
bool map[1001][1001],link[1001];
int match[1001];
int n;
__int64 a[1001];
int find(int u)
{
int i;
for(i=0;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
scanf("%I64d",&a[i]);
for(j=0;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
memset(link,false,sizeof(link));
sum+=find(i);
}
printf("%d\n",n-sum);
}
return 0;
}
#include
#include
bool map[1001][1001],link[1001];
int match[1001];
int n;
__int64 a[1001];
int find(int u)
{
int i;
for(i=0;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
scanf("%I64d",&a[i]);
for(j=0;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
memset(link,false,sizeof(link));
sum+=find(i);
}
printf("%d\n",n-sum);
}
return 0;
}