最小径径覆盖

最小路径覆盖

题目大意：给出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;
}