Prime Independence LightOJ - 1356

HK+质因子分解
HK是二分图匹配中匈牙利算法的优化，时间复杂度O(sqrt(n)*m)
先通过bfs寻找多条增广路，记下每个点到源点的距离（类似于网络流dinic算法），然后用类似于匈牙利算法中dfs的方法，进行匹配。
要求图是二分的，并且根据增广路的特性
模板：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N =5e5+5;
int t,n,n1,n2;//n1:左边的点数，n2:右边的点数
vector<int> g[N];//存图
int mx[N], my[N];//用来记左边点匹配的点，右边点匹配的点
queue<int> que;//bfs
int dx[N],dy[N],num[N],id[N];//dx:表示左边的点离源点的距离
bool vis[N];//dfs中用于标记
bool Find(int u)
{
    for(int i = 0; i < g[u].size(); i++)
    {
        if(!vis[g[u][i]] && dy[g[u][i]] == dx[u] + 1)
        {
            vis[g[u][i]] = true;
            if(!my[g[u][i]] || Find(my[g[u][i]]))
            {
                mx[u] = g[u][i];
                my[g[u][i]] = u;
                return true;
            }
        }
    }
    return false;
}
int Hmatch()
{
    memset(mx, 0, sizeof(mx));
    memset(my, 0, sizeof(my));
    int ans = 0;
    while(true)
    {
        bool flag = false;
        while(!que.empty())
            que.pop();
        memset(dx, 0, sizeof(dx));
        memset(dy, 0, sizeof(dy));
        for(int i = 1; i <= n1; i++)
            if(!mx[i])//增广路起源于左边的点
                que.push(i);
        while(!que.empty())
        {
            int u = que.front();
            que.pop();
            for(int i = 0; i < g[u].size(); i++)
                if(!dy[g[u][i]])
                {
                    dy[g[u][i]] = dx[u] + 1;
                    if(my[g[u][i]])
                    {
                        dx[my[g[u][i]]] = dy[g[u][i]] + 1;
                        que.push(my[g[u][i]]);
                    }
                    else 
                        flag = true;
                }
        }
        if(!flag) 
            break;//上面是寻找增广路
        memset(vis, 0, sizeof(vis));//走一条增广路
        for(int i = 1; i <= n1; i++)
         if(!mx[i]&&Find(i)) ans++;
    }
    return ans;
}
void init()
{
    n1=0,n2=0;
    scanf("%d",&n);
    memset(num, 0, sizeof(num));
    memset(id, 0, sizeof(id));
    for(int i=1;i<=n;i++) 
    {
        scanf("%d", &num[i]);
        g[i].clear();
    }
    sort(num+1, num+n+1);
}
int main()
{
    int cas = 0;
    scanf("%d",&t);
    while(t--)
    {
        init();
        for(int i = 1; i <= n; i++) {
            int factor[10000];
            int cnt=0,sum=0, k = num[i];
            for(int j = 2; k>1 && j*j<=k; j++)
            if(k%j==0)
            {
                    factor[cnt++] = j;
                    while(k%j==0) {
                            k/=j;
                            sum++;
                    }
            }
            if(k>1) {    //k有可能是质数
                     factor[cnt++]=k;
                     sum++;
           }
           if(sum % 2 == 0) id[num[i]] = (++n1);
           else id[num[i]] = (++n2);
           for(int j = 0; j < cnt; j++)
           {
                int c = num[i]/factor[j];
                if(id[c]) {
                    if(sum&1) g[id[c]].push_back(id[num[i]]);
                    else g[id[num[i]]].push_back(id[c]);
                }
           }
        }
        printf("Case %d: %d\n", ++cas, n - Hmatch());
    }
    return 0;
}