hdu 3335 （最小路徑覆蓋）

[cpp]
include"stdio.h"  
#include"string.h"  
#include"algorithm"  
using namespace std; 
int n; 
int map[1001][1001]; 
int v[1001],set[1001]; 
int dfs(int k) 
{ 
    int i; 
    for(i=0;i<n;i++) 
    { 
        if(!v[i]&&map[k][i]) 
        { 
            v[i]=1; 
            if(dfs(set[i])||set[i]==0) 
            { 
                set[i]=k; 
                return 1; 
            } 
        } 
    } 
    return 0; 
} 
int main() 
{ 
    __int64 a[1001]; 
    int T; 
    int i,j,m; 
    scanf("%d",&T); 
    while(T--) 
    { 
        scanf("%d",&n); 
        for(i=0;i<n;i++) 
            scanf("%I64d",&a[i]); 
        sort(a,a+n); 
        m=1; 
        for(i=1;i<n;i++) 
        { 
            if(a[i]!=a[i-1]) 
                a[m++]=a[i]; 
        } 
        n=m; 
        memset(map,0,sizeof(map)); 
        memset(set,0,sizeof(set)); 
        for(i=0;i<n;i++) 
        { 
            for(j=i+1;j<n;j++) 
                if(a[j]%a[i]==0)map[j][i]=1; 
        } 
        int ans=0; 
        for(i=0;i<n;i++) 
        { 
            memset(v,0,sizeof(v)); 
            if(dfs(i))ans++; 
        } 
        printf("%d\n",n-ans); 
    } 
    return 0; 
} 

#include"stdio.h"
#include"string.h"
#include"algorithm"
using namespace std;
int n;
int map[1001][1001];
int v[1001],set[1001];
int dfs(int k)
{
    int i;
    for(i=0;i<n;i++)
    {
        if(!v[i]&&map[k][i])
        {
            v[i]=1;
            if(dfs(set[i])||set[i]==0)
            {
                set[i]=k;
                return 1;
            }
        }
    }
    return 0;
}
int main()
{
    __int64 a[1001];
    int T;
    int i,j,m;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(i=0;i<n;i++)
            scanf("%I64d",&a[i]);
  sort(a,a+n);
        m=1;
        for(i=1;i<n;i++)
        {
            if(a[i]!=a[i-1])
                a[m++]=a[i];
        }
        n=m;
        memset(map,0,sizeof(map));
        memset(set,0,sizeof(set));
        for(i=0;i<n;i++)
        {
            for(j=i+1;j<n;j++)
                if(a[j]%a[i]==0)map[j][i]=1;
        }
        int ans=0;
        for(i=0;i<n;i++)
        {
            memset(v,0,sizeof(v));
            if(dfs(i))ans++;
        }
        printf("%d\n",n-ans);
    }
    return 0;
}