首页 > 代码库 > LightOJ 1356 Prime Independence（质因数分解+最大独立集+Hopcroft-Carp）
LightOJ 1356 Prime Independence（质因数分解+最大独立集+Hopcroft-Carp）
http://lightoj.com/login_main.php?url=volume_showproblem.php?problem=1356
题意：
给出n个数，问最多能选几个数，使得该集合中的任意两个数中其中一个数不是另一个质数倍。
思路：
二分图的最大独立集。
那么怎么建图呢？
我们按照质因数的奇偶性来分成两部分建图，如果两个数是质数倍的关系，那么就连边，最后最大独立集=点数-最大匹配。
对每个数进行质因数分解，存储每个质因数和质因数的总数，比如说P，质因数为x1，x2，x3...接下来我们去看是否存在P/x1，P/x2...是否存在。如果存在的话，首先还要判断一下他们的质因数奇偶性，因为质数倍的数只有一个质因数不同，所以肯定是一奇一偶。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<vector> 6 #include<queue> 7 #include<cmath> 8 #include<map> 9 #include<stack> 10 using namespace std; 11 12 const int maxn=500000+5; 13 const int INF=0x3f3f3f3f; 14 15 int n; 16 int cnt=0; 17 int primes[maxn]; 18 int vis[maxn]; 19 20 vector<int>g[40005]; 21 int um[maxn],vm[maxn]; 22 int dx[maxn],dy[maxn],dis; 23 24 void get_primes() 25 { 26 int m=sqrt(maxn+0.5); 27 for(int i=2;i<=m;i++) 28 { 29 if(!vis[i]) 30 { 31 for(int j=i*i;j<=maxn;j+=i) 32 vis[j]=1; 33 } 34 } 35 for(int i=2;i<=maxn;i++) 36 if(!vis[i]) primes[cnt++]=i; 37 } 38 39 bool searchP() 40 { 41 queue<int>q; 42 dis=INF; 43 memset(dx,-1,sizeof(dx)); 44 memset(dy,-1,sizeof(dy)); 45 for(int i=1;i<=n;i++) 46 if(um[i]==-1) 47 { 48 q.push(i); 49 dx[i]=0; 50 } 51 while(!q.empty()) 52 { 53 int u=q.front();q.pop(); 54 if(dx[u]>dis) break; 55 for(int i=0;i<g[u].size();i++) 56 { 57 int v = g[u][i]; 58 if(dy[v]==-1) 59 { 60 dy[v]=dx[u]+1; 61 if(vm[v]==-1) dis=dy[v]; 62 else 63 { 64 dx[vm[v]]=dy[v]+1; 65 q.push(vm[v]); 66 } 67 } 68 } 69 } 70 return dis!=INF; 71 } 72 73 bool dfs(int u) 74 { 75 for(int i=0;i<g[u].size();i++) 76 { 77 int v = g[u][i]; 78 if(!vis[v]&&dy[v]==dx[u]+1) 79 { 80 vis[v]=1; 81 if(vm[v]!=-1&&dy[v]==dis) continue; 82 if(vm[v]==-1||dfs(vm[v])) 83 { 84 vm[v]=u;um[u]=v; 85 return 1; 86 } 87 } 88 } 89 return 0; 90 } 91 92 int maxMatch() 93 { 94 int res=0; 95 memset(um,-1,sizeof(um)); 96 memset(vm,-1,sizeof(vm)); 97 while(searchP()) 98 { 99 memset(vis,0,sizeof(vis));100 for(int i=1;i<=n;i++)101 if(um[i]==-1&&dfs(i)) res++;102 }103 return res;104 }105 106 int a[maxn],b[maxn],p[maxn],num[maxn];107 108 int main()109 {110 //freopen("D:\\input.txt","r",stdin);111 int T;112 int kase=0;113 get_primes();114 scanf("%d",&T);115 while(T--)116 {117 scanf("%d",&n);118 for(int i=0;i<=n;i++) g[i].clear();119 memset(b,-1,sizeof(b));120 for(int i=1;i<=n;i++)121 scanf("%d",&a[i]);122 sort(a+1,a+1+n);123 for(int i=1;i<=n;i++)124 b[a[i]]=i;125 126 memset(num,0,sizeof(num));127 for(int i=1;i<=n;i++)128 {129 int x=a[i];130 int sum1=0;131 int sum2=0;132 for(int j=0;primes[j]*primes[j]<=x;j++)133 {134 if(x%primes[j]==0)135 {136 p[sum1++]=primes[j];137 while(x%primes[j]==0) {x/=primes[j];sum2++;}138 }139 }140 if(x>1) {p[sum1++]=x;sum2++;}141 num[i]=sum2;142 for(int j=0;j<sum1;j++)143 {144 int t=b[a[i]/p[j]];145 if(t<i&&t>0)146 {147 if((sum2&1)==(num[t]&1)) continue;148 if(sum2&1) g[i].push_back(t);149 else g[t].push_back(i);150 }151 }152 }153 154 printf("Case %d: %d\n",++kase,n-maxMatch());155 }156 157 return 0;158 }
LightOJ 1356 Prime Independence（质因数分解+最大独立集+Hopcroft-Carp）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。