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; }