HDU 3335-Divisibility（二分割図）

タイトル:
http://acm.hdu.edu.cn/showproblem.php?pid=3335
件名:
n個の数の中で互いに倍数でない最大集合を求めて、集合要素の個数を出力します。
考え方:
テーマは最大の独立点集に転化します。
AC.

#include 
#include 
#include 
#include 

using namespace std;
const int maxn = 1005;
long long num[maxn];
int g[maxn][maxn];
int n;

int linker[maxn];
bool used[maxn];
bool dfs(int u)
{
    for(int v = 0; v < n; ++v) {
        if(g[u][v] && !used[v]) {
            used[v] = true;
            if(linker[v] == -1 || dfs(linker[v])) {
                linker[v] = u;
                return true;
            }
        }
    }
    return false;
}
int hungray()
{
    int res = 0;
    memset(linker, -1, sizeof(linker));
    for(int u = 0; u < n; ++u) {
        memset(used, 0, sizeof(used));
        if(dfs(u)) res++;
    }

    return res;
}
int main()
{
    //freopen("in", "r", stdin);
    int T;
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for(int i = 0; i < n; ++i) {
            scanf("%I64d", &num[i]);
        }

        sort(num, num+n);
        memset(g, 0, sizeof(g));
        for(int i = 0; i < n; ++i) {
            for(int j = i+1; j < n; ++j) {
                if(num[j] % num[i] == 0) g[j][i] = 1;
            }
        }

        printf("%d
", n-hungray());
    }
    return 0;
}