`
huyifan951124
  • 浏览: 82885 次
社区版块
存档分类
最新评论

hihocoder1158 二分图的最大独立集

 
阅读更多

题目大意:中文题。

算法思路:首先找出每个数的质因数的个数,因为如果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);  //这个不可以缺少
}*/

 

0
0
分享到:
评论

相关推荐

    Hungary-algorithm.zip_二分图_匈牙利算法_最大独立集_权 二分图_赋权二分图

    “匈牙利算法”可以用于求解多种形式的指派 问题,其基本思想是寻找独立1元素组,而独立1 元素组与图论中对集是一个等价概念,所以与图论中求解赋权二分图最优对集、最大对集的思想是一脉相承的。

    二分图匹配及其运用.。。

    此外,二分图的最大独立集也是另一个相关的概念,指的是图中没有边相连的点的最大集合。最大独立集的大小等于顶点总数减去最大匹配数,这表明最大独立集和最小顶点覆盖是互补的。 总之,二分图匹配及其算法在图论和...

    二分图最大匹配及常用建图方法.pdf

    ### 二分图最大匹配及常用建图方法详解 #### 二分图概念与最大匹配问题 二分图,作为图论中的一种特殊结构,指的是一个图能够被划分为两个互不相交的集合,使得图中每条边的两个端点分别属于这两个不同的集合。在...

    二分图匹配算法总结1

    匈牙利算法是解决二分图最大匹配问题的一种经典方法,由Edmonds在1965年提出。算法的核心思想是通过寻找增广路径来逐步增加匹配的数量。增广路径是一种特殊的交错路径,其首尾未匹配,中间交替出现未匹配和已匹配的...

    二分图匹配问题(匈牙利及KM算法)

    匈牙利算法,由匈牙利数学家Edmonds于1965年提出,是一种求解二分图最大匹配的有效方法。算法的关键在于增广路径,即一条连接两个未匹配顶点的路径,路径上的边按照匹配和未匹配交替出现。增广路径的存在意味着可以...

    二分图算法

    匈牙利算法,也称为Kuhn-Munkres算法或KM算法,是求解二分图最大匹配问题的有效方法。这个算法是由两位匈牙利数学家Edmund Landau(化名David Kuhn)和Juliusz Munkres分别独立提出的,因此得名。在许多实际问题中,...

    二分图最优匹配matlab代码.zip

    在二分图中,最优匹配是指找到最大数量的相互独立的边,这些边不会形成环,并且最大化匹配的边数。 二分图最优匹配的典型算法包括匈牙利算法(Kuhn-Munkres算法)和Dijkstra的增广路径算法。匈牙利算法是一种求解...

    二分图覆盖与独立集ppt

    网络流ppt,最小点覆盖,König定理:二分图中的最大匹配数=这个图中的最小点覆盖数,König定理证明,最小点覆盖构造

    二分图匹配

    - **定理**:在任何二分图中,最大匹配的边数等于最小边覆盖集的边数。 - **证明**:这一关系可以通过Hall's Marriage Theorem等理论来证明,它表明了在特定条件下,最大匹配的存在性与图的结构之间存在着密切的联系...

    二分图匹配匈牙利算法和KM算法简介.pptx

    二分图匹配匈牙利算法和KM算法是解决二分图最大匹配问题的两种方法,匈牙利算法可以解决普通二分图的最大匹配问题,KM算法可以解决带权完全二分图的最大匹配问题。这两种算法都广泛应用于实际模型中,解决了许多实践...

    二分图(匈牙利算法)归纳.md

    1. **匈牙利算法**:该算法是一种高效的求解二分图最大匹配问题的方法,时间复杂度为\(O(nm)\),其中\(n\)是顶点数量,\(m\)是边的数量。 - **0要素**:表示不存在匹配的顶点。 - **1要素**:表示已经成功匹配的...

    二部图概述(二分图,匹配,覆盖,KM算法)

    二分图的最大匹配,匈牙利算法,最小点覆盖,DAG图的最小路径覆盖。二分图的最大独立集.二分图最优匹配.noi,acm,基础

    二分图的最大匹配经典之匈牙利算法[定义].pdf

    二分图最大匹配的经典算法,即匈牙利算法,是一种高效地解决特定图论问题的方法,广泛应用于软件开发中。二分图是由两个独立部分组成的图,其中任意两点之间不存在内部连接。这种图的特点和性质使得它在解决匹配问题...

    ISP.rar_matlab_图独立集_最大独立集_模拟退火_独立集问题

    独立集是指图 G 中两两互不相邻的顶点构成的集合。任意有关图中团的性质都能很自然的转述成独立...一般而言,寻找图的最大团是 NP 困难的,从而寻找图的最大独立集也是 NP 困难的。用模拟退火算法找出图的最大独立集。

    线性规划与网络流题解

    问题编号 问题名称 问题模型 转化模型 1 飞行员配对方案问题 二分图最大匹配 网络最大流 2 太空飞行计划问题 最大权闭合图 网络最小割 3 最小路径覆盖问题 有向无环图...24 骑士共存问题 二分图最大独立集 网络最小割

    6. 二分图与平面图 -PPT.pptx

    二分图提供了一种将图结构分为两个独立部分的方法,而平面图则允许我们在二维空间中无冲突地表示复杂网络。这两个概念在算法设计、数据结构、计算机图形学以及工程问题等领域都有着深远的影响。理解并掌握这些知识,...

    一个求解简单超图中最大独立集的算法.pdf

    2. **独立集**:在图论中,独立集是指图中没有任何两个顶点直接相连的一组顶点。 3. **极大独立集**:指在所有独立集中,包含顶点数最多的独立集,但不一定是最优的(即可能不是最大独立集)。 4. **最大独立集**...

    2分图最大匹配算法,很不错啊

    综上所述,二分图最大匹配算法是图论中的核心工具,它在解决匹配、覆盖、独立集以及带权优化问题时起着关键作用。通过匈牙利算法、Konig定理和KM算法等方法,我们可以有效地在各种实际场景中找到最优解决方案。

    二分图匹配-匈牙利算法和KM算法简介 精品资料.pptx

    一个关于二分图的性质:最大匹配数+最大独立集=X+Y最佳匹配。如果边上带权的话,找出权和最大的匹配叫做求最佳匹配。 KM算法:KM算法是一种求最佳匹配的算法,它的主要思想是通过寻找可行顶标来找到最佳匹配。...

Global site tag (gtag.js) - Google Analytics