[最小路径覆盖]hdoj 3335：Divisibility
大致题意：
? ? 给出不超过1000个数字，现在要取出k个数字，使得这k个数字两两之间互质，问k最大是多少。
?
大致思路：?
? ? 把问题转化为二分图最大匹配问题，把每个点i拆做 i 和 i' ，如果a>b且a可以整除b则连接a->b'。求出最小路径覆盖即可。
?
#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>using namespace std;const int nMax=1005;int n,m;long long num[nMax];bool map[nMax][nMax];bool vis[nMax];int linkk[nMax];int dfs(int s){for(int i=0;i<m;i++){if(!vis[i]&&map[s][i]){vis[i]=1; if(linkk[i]==-1||dfs(linkk[i])){linkk[i]=s; return 1;}}}return 0;}int main(){int cas,i,j;cin>>cas;while(cas--){cin>>n;m=n;memset(map,0,sizeof(map));for(i=0;i<n;i++){cin>>num[i];}sort(num,num+n);for(i=n-1;i>=0;i--){for(j=0;j<i;j++){if(num[i]%num[j]==0){map[i][j]=1;}}}int ans=0;memset(linkk,-1,sizeof(linkk));for(i=0;i<n;i++){memset(vis,0,sizeof(vis));if(dfs(i))ans++;}ans=n-ans;cout<<ans<<endl;}return 0;}??
?