大致题意:
给出不超过1000个数字,现在要取出k个数字,使得这k个数字两两之间互质,问k最大是多少。
大致思路:
把问题转化为二分图最大匹配问题,把每个点i拆做 i 和 i' ,如果a>b且a可以整除b则连接a->b'。求出最小路径覆盖即可。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int nMax=1005;
int n,m;
long long num[nMax];
bool map[nMax][nMax];
bool vis[nMax];
int linkk[nMax];
int dfs(int s){
for(int i=0;i<m;i++){
if(!vis[i]&&map[s][i]){
vis[i]=1;
if(linkk[i]==-1||dfs(linkk[i])){
linkk[i]=s;
return 1;
}
}
}
return 0;
}
int main(){
int cas,i,j;
cin>>cas;
while(cas--){
cin>>n;
m=n;
memset(map,0,sizeof(map));
for(i=0;i<n;i++){
cin>>num[i];
}
sort(num,num+n);
for(i=n-1;i>=0;i--){
for(j=0;j<i;j++){
if(num[i]%num[j]==0){
map[i][j]=1;
}
}
}
int ans=0;
memset(linkk,-1,sizeof(linkk));
for(i=0;i<n;i++){
memset(vis,0,sizeof(vis));
if(dfs(i))ans++;
}
ans=n-ans;
cout<<ans<<endl;
}
return 0;
}
分享到:
相关推荐
2. **算法类型**:包括排序(冒泡、快速、归并等)、搜索(深度优先、广度优先、二分查找等)、动态规划、贪心算法、回溯、图论(最小生成树、最短路径等)等。 3. **数据结构**:数组、链表、栈、队列、树(二叉树...
根据给定的文件信息,我们可以总结出以下关于“hdoj2066最短路径”的相关知识点: ## hdoj2066最短路径概述 ### 标题解析:“hdoj2066最短路” - **hdoj**:High Density Online Judge(高密度在线评测系统),是...
《HDOJ离线版:探索编程竞赛的智慧宝库》 HDOJ,全称为“杭州电子科技大学在线评测系统”(Hangzhou Dianzi University Online Judge),是中国早期的编程竞赛平台之一,深受广大编程爱好者和在校学生的喜爱。HDOJ...
【标题】"hdoj.rar_Dividing HDOJ_OJ 1082_hdoj 10_杭电oj_杭电oj1000" 涉及的知识点主要围绕着“杭电在线判题系统(HDOJ)”以及其中的题目1082和10系列题目。HDOJ是杭州电子科技大学主办的一个在线编程竞赛平台,...
HDOJ1000.java HDOJ1001.java HDOJ1089.java HDOJ1090.java HDOJ1091.java HDOJ1092.java HDOJ1093.java HDOJ1094.java HDOJ1095.java HDOJ1108.java HDOJ1406.java HDOJ2001.java HDOJ2002.java HDOJ2003.java HDOJ...
【标题】"HDOJ 80题 Java"是一份专为Java程序员设计的在线编程挑战集合,源自杭州电子科技大学(HDOJ)的在线评测系统。这些题目旨在帮助Java开发者提升算法理解与编程能力,同时也为那些习惯于C++但希望在Java环境...
"hdoj--acm题目,有注释" 本资源提供了多个 ACM 题目的解决方案,代码都带有注释,非常适合初学者学习。下面是对每个题目的知识点总结: 2000:本题目要求输入三个字符,输出按照从小到大排序的结果。本代码使用了...
3. **图论**:包括最短路径算法(Dijkstra、Floyd-Warshall、Bellman-Ford)、拓扑排序、最小生成树(Prim、Kruskal)等。 4. **数据结构**:如链表、栈、队列、树(二叉树、平衡树如AVL、红黑树)、图、堆、哈希表...
ACM ICPC HDOJ1002
ACM ICPC HDOJ1001
【ACM HDOJ 课件】是一套涵盖了多种计算机科学竞赛中常见算法与理论的教育资源,主要针对ACM(国际大学生程序设计竞赛)和HDOJ(华中地区大学生在线编程题库)的训练。这些课件深入浅出地讲解了在解决复杂问题时所需...
hdoj1001标程
hdoj1004,解题代码,答案代码,欢迎下载
【标题解析】:“hdoj 2013 多校训练4标程+解题报告”这个标题表明,这是一个关于2013年Happy Dream Online Judge(简称hdoj)组织的多校联合编程训练的资料。"4标程"意味着包含了四道题目(或者可能是四个阶段)的...
ACM ICPC HDOJ1003
ACM ICPC HDOJ1008
【OJ.tar.gz_HDOJ _OJ源码_oj】是一个包含编程竞赛平台HDOJ(Happy Ding Octopus Judge)部分源代码的压缩文件。这个压缩包的主要目的是供学习和研究使用,尤其是针对50至60题目的解题算法和系统实现。通过分析这些...
hdoj-problem-archive 杭电OJ题目源码记录 —— a source code of hdoj acm problem archive 简介 此项目为 的 题目以及代码仓库 src 中每一个文件夹代表一个题目 每个文件夹中都有 原题文档介绍.md 原题文档介绍.md...
### hdoj1002——大整数相加 #### 题目背景与目的 本题目来源于杭州电子科技大学的在线评测系统(HDOJ),编号为1002的大整数相加问题。该题目主要考察的是编程者对于大整数处理的基本技巧以及对数组、循环等基础...
ACM ICPC HDOJ1000