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

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
分享到:
评论

相关推荐

    matlab实现匈牙利算法二分图最大匹配的程序

    标题中的“matlab实现匈牙利算法二分图最大匹配的程序”指的是使用MATLAB编程语言来实现一种经典的图论算法——匈牙利算法,它主要用于解决二分图的最大匹配问题。二分图是一种特殊的图,其中的节点可以分为两个不...

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

    二分图最大匹配与其他图论概念紧密相关,如最大独立集和最小顶点覆盖。最大独立集是在二分图中找一个最大的点集,其中任意两点都不相邻,它的大小与最大匹配数有特定关系:最大匹配数加最大独立集的大小等于节点总数...

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

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

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

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

    二分图匹配算法总结1

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

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

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

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

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

    最大独立集 C语言

    最大独立集和最大团的关系是,一个图的最大独立集和其补图的最大团大小相等。利用这一点,可以互相转换问题,从而寻找解决方案。 图的着色问题则与最大独立集有间接联系。给定一个图,我们需要用最少的颜色给每个...

    线性规划与网络流题解

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

    ACM讲课之二分图匹配匈牙利算法学习教案.pptx

    匈牙利算法是解决无权二分图最大匹配问题的经典算法之一。该算法的核心思想是通过不断寻找所谓的“增广路径”来逐步扩大匹配集M的大小,直到无法再找到增广路径为止。 **关键概念:** - **盖点**:指那些被当前匹配...

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

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

    论文研究-图论中最大独立集问题的精确算法.pdf

    尽管已经有许多学者提出了多种精确算法来解决最大独立集问题,但由于问题规模的增长和图中节点数量的增加,这些算法的时间复杂度也随之升高。为了克服这一挑战,研究者们不断探索新的技术来提高算法效率。 #### ...

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

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

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

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

    一种启发式的分布式最大独立集算法.pdf

    最大独立集问题在计算机科学与数学领域中是一个基础而重要的问题,尤其在通信网络资源分配等方面具有广泛的应用。这个问题可以用图论的语言描述:在一个无向图中找到最大的独立集,即最大的节点集合,其中任意两个...

    个性化推荐算法系统(2):基于二分图的个性化推荐召回算法personal rank(MovieLens数据集电影推荐)

    二分图是一种特殊的图结构,其中的节点可以分为两个独立的集合,且任意两个节点间的边都连接不同集合的节点。在推荐系统中,一个典型的二分图可能是用户集和物品集,边代表用户对物品的评价或交互。 Personal Rank...

    课程作业时的求出二分图匹配前N个最优解的算法matlab源程序

    在图论中,二分图是一种特殊的图结构,其中的节点可以被分为两个独立的集合,所有边都连接不同集合中的节点。二分图匹配问题就是要找到尽可能多的互不相交的边,使得每个节点最多只参与一条边。这在许多实际问题中都...

    二分匹配题集

    以上题型涵盖了二分图匹配问题的主要方面,包括最大匹配、最小点覆盖、最小路径覆盖、行列匹配等,同时也涉及到了更高级的问题如多重匹配、最大独立集等。通过练习这些题目,可以加深对二分图匹配算法的理解,并提高...

Global site tag (gtag.js) - Google Analytics