题目大意:中文题。
算法思路:首先找出每个数的质因数的个数,因为如果a和b是质数相关的话,那他们两个的质数的个数肯定是一奇,一偶,因此我们可以根据这个性质,将这些数分成两个部分,转化二分图的最大独立集求解,这道题我已开始用求解质因数的模板,结果发现这个模板对于相同的质因数只算一个(在这里wa了好多回=- =),后来只好打素数表求解。。。
#include<iostream> #include<cstdio> #include<cstring> #include<vector> #include<queue> using namespace std; #define MAXN 1005 #define MAXN2 5500000 int t,n,e,size1,size2; int a[MAXN],match[MAXN],head[MAXN],nextt[MAXN]; int s1[MAXN],s2[MAXN]; bool maps[MAXN][MAXN]; bool visited2[MAXN]; typedef struct Edge { int u,v,c; }; Edge edges[MAXN]; /** * 线性筛法求素数表 * 复杂度: O(n) */ int prime[MAXN2] = {0},num_prime = 0; bool isNotPrime[MAXN2] = {true, true}; void GetPrime_Init()//初始化调用 { for(int i = 2 ; i < MAXN2 ; i ++) { if(! isNotPrime[i]) prime[num_prime ++]=i; for(int j = 0 ; j < num_prime && i * prime[j] < MAXN2 ; j ++) { isNotPrime[i * prime[j]] = true; if( !(i % prime[j])) break; } } } bool isPrime(int x) { for(int i=2;i*i<=x;i++) { if(x%i==0) return false; } return true; } void addNode(int u,int v,int c) { edges[e].u=u; edges[e].v=v; edges[e].c=c; nextt[e]=head[u]; head[u]=e++; } int dfs(int p) { for(int i=head[p];i+1;i=nextt[i]){ int v=edges[i].v; if(visited2[v]) continue; visited2[v]=1; if(match[v]==-1||dfs(match[v])){ match[v]=p; return 1; } } return 0; } void solve_div(int kk) { int kk2=kk; int num=0; for(int i=0;prime[i]<=kk;i++) { while(kk%prime[i]==0) { num++; kk/=prime[i]; } } if(num%2!=0) { s1[size1++]=kk2; } else { s2[size2++]=kk2; } } int main() { GetPrime_Init(); scanf("%d",&t); int cnt=0; while(t--) { size1=0,size2=0,e=0; memset(s1,0,sizeof(s1)); memset(s2,0,sizeof(s2)); memset(maps,false,sizeof(maps)); memset(match,-1,sizeof(match)); memset(head,-1,sizeof(head)); memset(nextt,-1,sizeof(nextt)); scanf("%d",&n); for(int i=1; i<=n; i++) { scanf("%d",&a[i]); } for(int i=1;i<=n;i++) { solve_div(a[i]); } for(int i=0;i<size1;i++) { for(int j=0;j<size2;j++) { if(s1[i]%s2[j]==0&&isPrime(s1[i]/s2[j])) { addNode(i,j,1); } else if(s2[j]%s1[i]==0&&isPrime(s2[j]/s1[i])) { addNode(i,j,1); } } } int sum=0; for(int i=0;i<size1;i++) { memset(visited2,false,sizeof(visited2)); sum+=dfs(i); } printf("Case #%d: %d\n",++cnt,n-sum); } return 0; }
在这里再记录一下那个只记录一次的求解质因数的模板。
/*void Solve(int nn,int k)//利用容斥原理求解质因数 { v[k].clear(); for(int i=2; i*i<=nn; i++) { if(nn%i==0) { v[k].push_back(i); while(nn%i==0) nn/=i; } } if(nn>1) v[k].push_back(nn); //这个不可以缺少 }*/
相关推荐
“匈牙利算法”可以用于求解多种形式的指派 问题,其基本思想是寻找独立1元素组,而独立1 元素组与图论中对集是一个等价概念,所以与图论中求解赋权二分图最优对集、最大对集的思想是一脉相承的。
此外,二分图的最大独立集也是另一个相关的概念,指的是图中没有边相连的点的最大集合。最大独立集的大小等于顶点总数减去最大匹配数,这表明最大独立集和最小顶点覆盖是互补的。 总之,二分图匹配及其算法在图论和...
### 二分图最大匹配及常用建图方法详解 #### 二分图概念与最大匹配问题 二分图,作为图论中的一种特殊结构,指的是一个图能够被划分为两个互不相交的集合,使得图中每条边的两个端点分别属于这两个不同的集合。在...
匈牙利算法是解决二分图最大匹配问题的一种经典方法,由Edmonds在1965年提出。算法的核心思想是通过寻找增广路径来逐步增加匹配的数量。增广路径是一种特殊的交错路径,其首尾未匹配,中间交替出现未匹配和已匹配的...
匈牙利算法,由匈牙利数学家Edmonds于1965年提出,是一种求解二分图最大匹配的有效方法。算法的关键在于增广路径,即一条连接两个未匹配顶点的路径,路径上的边按照匹配和未匹配交替出现。增广路径的存在意味着可以...
匈牙利算法,也称为Kuhn-Munkres算法或KM算法,是求解二分图最大匹配问题的有效方法。这个算法是由两位匈牙利数学家Edmund Landau(化名David Kuhn)和Juliusz Munkres分别独立提出的,因此得名。在许多实际问题中,...
在二分图中,最优匹配是指找到最大数量的相互独立的边,这些边不会形成环,并且最大化匹配的边数。 二分图最优匹配的典型算法包括匈牙利算法(Kuhn-Munkres算法)和Dijkstra的增广路径算法。匈牙利算法是一种求解...
网络流ppt,最小点覆盖,König定理:二分图中的最大匹配数=这个图中的最小点覆盖数,König定理证明,最小点覆盖构造
- **定理**:在任何二分图中,最大匹配的边数等于最小边覆盖集的边数。 - **证明**:这一关系可以通过Hall's Marriage Theorem等理论来证明,它表明了在特定条件下,最大匹配的存在性与图的结构之间存在着密切的联系...
二分图匹配匈牙利算法和KM算法是解决二分图最大匹配问题的两种方法,匈牙利算法可以解决普通二分图的最大匹配问题,KM算法可以解决带权完全二分图的最大匹配问题。这两种算法都广泛应用于实际模型中,解决了许多实践...
1. **匈牙利算法**:该算法是一种高效的求解二分图最大匹配问题的方法,时间复杂度为\(O(nm)\),其中\(n\)是顶点数量,\(m\)是边的数量。 - **0要素**:表示不存在匹配的顶点。 - **1要素**:表示已经成功匹配的...
二分图的最大匹配,匈牙利算法,最小点覆盖,DAG图的最小路径覆盖。二分图的最大独立集.二分图最优匹配.noi,acm,基础
二分图最大匹配的经典算法,即匈牙利算法,是一种高效地解决特定图论问题的方法,广泛应用于软件开发中。二分图是由两个独立部分组成的图,其中任意两点之间不存在内部连接。这种图的特点和性质使得它在解决匹配问题...
独立集是指图 G 中两两互不相邻的顶点构成的集合。任意有关图中团的性质都能很自然的转述成独立...一般而言,寻找图的最大团是 NP 困难的,从而寻找图的最大独立集也是 NP 困难的。用模拟退火算法找出图的最大独立集。
问题编号 问题名称 问题模型 转化模型 1 飞行员配对方案问题 二分图最大匹配 网络最大流 2 太空飞行计划问题 最大权闭合图 网络最小割 3 最小路径覆盖问题 有向无环图...24 骑士共存问题 二分图最大独立集 网络最小割
二分图提供了一种将图结构分为两个独立部分的方法,而平面图则允许我们在二维空间中无冲突地表示复杂网络。这两个概念在算法设计、数据结构、计算机图形学以及工程问题等领域都有着深远的影响。理解并掌握这些知识,...
2. **独立集**:在图论中,独立集是指图中没有任何两个顶点直接相连的一组顶点。 3. **极大独立集**:指在所有独立集中,包含顶点数最多的独立集,但不一定是最优的(即可能不是最大独立集)。 4. **最大独立集**...
综上所述,二分图最大匹配算法是图论中的核心工具,它在解决匹配、覆盖、独立集以及带权优化问题时起着关键作用。通过匈牙利算法、Konig定理和KM算法等方法,我们可以有效地在各种实际场景中找到最优解决方案。
一个关于二分图的性质:最大匹配数+最大独立集=X+Y最佳匹配。如果边上带权的话,找出权和最大的匹配叫做求最佳匹配。 KM算法:KM算法是一种求最佳匹配的算法,它的主要思想是通过寻找可行顶标来找到最佳匹配。...