最小路径覆盖
题目大意：给出N（1000）个数字（<2^63 -1），从n中取出k个数，使得任意a，b属于k，a，b不形成整除关系。问k最大是多少
算法：有向图最小路径覆盖数
思路：因为要求取出一些点，使得他们之间没有整除关系，很容易想到利用整除关系建立一个图，然后看最多有多少个点能不相连，如果把图看作无向图，那么就很难想到做法，至少无向图最大点独立集是不能在1000的规模下运行的。如果a是b的约束，我们建立一条a向b的有向边，最后发现，要求的其实就是最小路径覆盖数。
最小路径覆盖数：在一个有向图中至少放几个人才能走到所有点（延边走，人可以放在任意位置，非官方解释）。
最小路径覆盖：在一个有向图中，最少用几条路径能把所有的点覆盖（路径不交叉，即每个点只属于一条路）。
当有向图无环时，可以用二分图最大匹配来求解。
最少路径覆盖=点数 – 二分图最大匹配
代码：
#include <iostream>#include <algorithm>#include <cmath>using namespace std;const int MAXN=1010;int uN,vN; int map[MAXN][MAXN];int match[MAXN];bool visit[MAXN]; bool search(int u){ int v; for(v=0;v<vN;v++) if(map[u][v]&&!visit[v]){ visit[v]=true; if(match[v]==-1||search(match[v])){ match[v]=u; return true; } } return false;}int hungary(){ int res=0; int u; memset(match,-1,sizeof(match)); for(u=0;u<uN;u++){ memset(visit,0,sizeof(visit)); if(search(u)) res++; } return res;}bool cmp(long long a, long long b){ return a > b;}long long a[1010];int main(){ int t; int n; int i, j; scanf("%d", &t); while(t --){ scanf("%d", &n); for(i = 0; i < n; i ++){ scanf("%I64d", &a[i]); } memset(map, 0, sizeof(map)); sort(a,a+n,cmp); uN = n; vN = n; for(i = 0; i < n ; i ++){ for(j = i + 1; j < n; j ++){ if(a[i]%a[j] == 0){ map[i][j] = 1; } } } int ans = n - hungary(); printf("%d\n", ans); } return 0;}