題意：

找出一個(gè)集合中的最大獨(dú)立集，任意兩數(shù)字之間不能是素?cái)?shù)倍數(shù)的關(guān)系。

思路：

最大獨(dú)立集，必然是二分圖。

最大數(shù)字50w，考慮對(duì)每個(gè)數(shù)質(zhì)因子分解，然后枚舉所有除去一個(gè)質(zhì)因子后的數(shù)是否存在，存在則建邊，考慮到能這樣建邊的數(shù)一定是質(zhì)因子個(gè)數(shù)奇偶不同，所以相當(dāng)于按奇偶區(qū)分建立了二分圖，然后求二分圖最大匹配，得到最大獨(dú)立集就行了。

有一點(diǎn)這個(gè)題數(shù)據(jù)比較大，直接匈牙利炸了，要Hopcroft-Karp優(yōu)化才能過(guò)。

#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <cmath> #include <string> #include <stack> #include <queue> #include <vector> #include <map> #define inf 0x3f3f3f3f #define met(a,b) memset(a,b,sizeof a) #define pb push_back using namespace std; typedef long long ll; const int N = 5e4+10; int n,m,sum,res,flag; bool mark[10*N]; int pri[N],cnt; void SP() {cnt=0;memset(mark,true,sizeof(mark));mark[0]=mark[1]=false;for(int i=2; i<10*N; i++){if(mark[i])pri[cnt++]=i;for (int j=0; (j<cnt)&&(i*pri[j]<10*N); j++){mark[i*pri[j]]=false;if (i%pri[j]==0)break;}} } int pos[10*N],num[N]; int f[N]; int vm[N],um[N]; bool vis[N]; vector<int>g[N]; int dx[N],dy[N],dis; void init() {n=m=0;memset(pos,0,sizeof(pos));memset(f,-1,sizeof(f));memset(vm,-1,sizeof(vm));memset(um,-1,sizeof(um));for(int i=0; i<=sum; i++)g[i].clear(); } void inserts(int u, int v) {g[u].push_back(v); } bool searchP() {queue<int>q;dis=inf;memset(dx,-1,sizeof(dx));memset(dy,-1,sizeof(dy));for(int i=1; i<=sum; i++)if(um[i]==-1){q.push(i);dx[i]=0;}while(!q.empty()){int u=q.front();q.pop();if(dx[u]>dis) break;for(int i=0; i<g[u].size(); i++){int v = g[u][i];if(dy[v]==-1){dy[v]=dx[u]+1;if(vm[v]==-1) dis=dy[v];else{dx[vm[v]]=dy[v]+1;q.push(vm[v]);}}}}return dis!=inf; } bool dfs(int u) {for(int i=0; i<g[u].size(); i++){int v = g[u][i];if(!vis[v]&&dy[v]==dx[u]+1){vis[v]=1;if(vm[v]!=-1&&dy[v]==dis) continue;if(vm[v]==-1||dfs(vm[v])){vm[v]=u;um[u]=v;return 1;}}}return 0; } int maxMatch() {int res=0;while(searchP()){memset(vis,0,sizeof(vis));for(int i=1; i<=sum; i++)if(um[i]==-1&&dfs(i)) res++;}return res; } int tmp[N],now,all; void solve(int t,int tot) {now = all = 0;int tt=t;for(int i=0; i<cnt&&pri[i]*pri[i]<=tt; i++){if(tt%pri[i]==0)tmp[now++] = pri[i];while(tt%pri[i]==0)tt/=pri[i],all++;}if(tt>1)tmp[now++] = tt, all++;f[tot]=1&all;if(f[tot])n++;else m++;for(int i=0; i<now; i++){int x=t/tmp[i];if(pos[x]){if(!f[tot])inserts(tot,pos[x]);else inserts(pos[x],tot);}} } int main() {int i,j,k,cas,T,t,x,y,z;SP();scanf("%d",&T);cas=0;while(T--){scanf("%d",&sum);init();for(i=1; i<=sum; i++)scanf("%d",&num[i]);for(i=1; i<=sum; i++)pos[num[i]] = i;for(i=1; i<=sum; i++)solve(num[i],i);printf("Case %d: %d\n",++cas,sum-maxMatch());}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/jianrenfang/p/6557157.html

總結(jié)

以上是生活随笔為你收集整理的Lightoj-1356 Prime Independence(质因子分解)（Hopcroft-Karp优化的最大匹配）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。