[hihoCoder] #1158 : 质数相关

时间限制:2000ms

单点时限:1000ms

内存限制:256MB

描述

两个数a和 b (a<b)被称为质数相关，是指a × p = b，这里p是一个质数。一个集合S被称为质数相关，是指S中存在两个质数相关的数，否则称S为质数无关。如{2, 8, 17}质数无关，但{2, 8, 16}, {3, 6}质数相关。现在给定一个集合S，问S的所有质数无关子集中，最大的子集的大小。

输入

第一行为一个数T，为数据组数。之后每组数据包含两行。

第一行为N，为集合S的大小。第二行为N个整数，表示集合内的数。

输出

对于每组数据输出一行，形如"Case #X: Y"。X为数据编号，从1开始，Y为最大的子集的大小。

数据范围

1 ≤ T ≤ 20

集合S内的数两两不同且范围在1到500000之间。

小数据

1 ≤ N ≤ 15

大数据

1 ≤ N ≤ 1000

样例输入

3
5
2 4 8 16 32
5
2 3 4 6 9
3
1 2 3

样例输出

Case #1: 3
Case #2: 3
Case #3: 2

编程之美2015初赛第一场第三题，找二分图的最大独立集，大小为：点的个数 - 最大匹配。

#include <bits/stdc++.h>
using namespace std;

int T, N;
vector<int> v;
vector<vector<int>> graph;
vector<int> link;
vector<bool> visited;
bool *isPrime;

void getPrime() {
    isPrime = new bool[500001];
    memset(isPrime, true, sizeof(bool) * 500001);
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i * i < 500001; ++i) if (isPrime[i]) {
        for (int j = 2; i * j < 500001; ++j) isPrime[i * j] = false;
    }
}

int dfs(int u) {
    for (auto v : graph[u]) if (!visited[v]) {
        visited[v] = true;
        if (link[v] == -1 || dfs(link[v])) {
            link[v] = u;
            return 1;
        }
    }
    return 0;
}

int hungary() {
    int res = 0;
    for (int i = 0; i < N; ++i) {
        visited.assign(N + 1, false);
        res += dfs(i);
    }
    return res / 2;
}

int main() {
    getPrime();
    cin >> T;
    for (int t = 1; t <= T; ++t) {
        cin >> N;
        v.resize(N);
        for (int i = 0; i < N; ++i) {
            cin >> v[i];
        }
        sort(v.begin(), v.end());
        graph.assign(N + 1, vector<int>());
        link.assign(N + 1, -1);
        for (int i = 0; i < N - 1; ++i) {
            for (int j = i + 1; j < N; ++j) {
                if (v[j] % v[i] == 0) {
                    int tmp = v[j] / v[i];
                    if (isPrime[tmp]) {
                        graph[i].push_back(j);
                        graph[j].push_back(i);
                    }
                }
            }
        }
        cout << "Case #" << t << ": ";
        int res = hungary();
        cout << N - res << endl;
    }
    return 0;
}