ACM图论解题报告集合

图论

1 题意：

输入cas n m 输入n个数 输入m组 每组表示一个范围内l r 中小于num的数的个数 注意从l是0开始的

思路 ：区间内找数 很容易联想到划分树 划分树是用来求一个区间内的第k大的数那我们可以找出第1第2第3.。。。。。。大数的值 和num进行比较用二分法很容易找到第几大的数小于且等于num

#include<stdio.h>

#include<algorithm>

using namespace std;

#define M 100005

int tree[40][M],sorted[M];

int toLeft[40][M];

void build(int level,int left,int right){

if(left==right)return ;

int mid=(left+right)>>1;

int i;

int suppose;//假设在中位数sorted[mid]左边的数都全部小于sorted[mid]

suppose=mid-left+1;

for(i=left;i<=right;i++){

if(tree[level][i]<sorted[mid]){

suppose--;

}

}

//如果suppose==1，则说明数组中值为sorted[mid]只有一个数。比如序列：1 3 4 5 6，sorted[mid]=4

/*如果suppose>1，则说明数组中左半边值为sorted[mid]的不止一个数,为mid-suppose。比如序列：1 4 4 4 6，sorted[mid]=4

*/

int lpos=left,rpos=mid+1;

for(i=left;i<=right;i++){

if(i==left)

{//这里是预处理，相当与初始化

toLeft[level][i]=0;

}

else

{

toLeft[level][i]=toLeft[level][i-1];

}

if(tree[level][i]<sorted[mid]){//划分到中位数左边

toLeft[level][i]++;

tree[level+1][lpos++]=tree[level][i];

}else if(tree[level][i]>sorted[mid]){//划分到中位数右边

tree[level+1][rpos++]=tree[level][i];

}else{//这里，suppose大于0的数划分到中位数的左边

if(suppose!=0){//这里的处理太巧妙了！帅气！

suppose--;

toLeft[level][i]++;

tree[level+1][lpos++]=tree[level][i];

}else{//表示

tree[level+1][rpos++]=tree[level][i];

}

}

}

build(level+1,left,mid);

build(level+1,mid+1,right);

}

//在[left,right]数据中查询[qleft,qright]中第k大的数据

int query(int level,int left,int right,int qleft,int qright,int k){

if( qleft==qright)

return tree[level][qleft];

int s;//代表[left,qleft)之间有多个个元素被分到左边

int ss;//[qleft, qright]内将被划分到左子树的元素数目

int mid=(left+right)>>1;

if(left==qleft){

s=0;

ss=toLeft[level][qright];

}else{

s=toLeft[level][qleft-1];

ss=toLeft[level][qright]-s;

}

int newl,newr;

if(k<=ss){//查询左边

newl=left+s;

newr=left+s+ss-1;

return query(level+1,left,mid,newl,newr,k);

}else{//查询右边

newl=mid-left+1+qleft-s;

newr=mid-left+1+qright-s-ss;

return query(level+1,mid+1,right,newl, newr,k - ss);

}

}

int main()

{

int n,m,cas,ca=0;

scanf("%d",&cas);

while(cas--)

{

printf("Case %d:\n",++ca);

scanf("%d %d",&n,&m);

int i;

for(i=1;i<=n;i++){

scanf("%d",&tree[0][i]);

sorted[i]=tree[0][i];

}

sort(sorted+1,sorted+n+1);

build(0,1,n);

int ql,qr,num,ans=0;

for(i=0;i<m;i++)

{

scanf("%d %d %d",&ql,&qr,&num);

ql++;qr++;//注意这里哦 题意是按从0开始的

int mid,left=1,right=qr-ql+1,ans=0;

mid=(left+right)/2;

while(left<=right)//别少了等于号

{

mid=(left+right)/2;

if(query(0,1,n,ql,qr,mid)>num) right=mid-1;

else {ans=mid;left=mid+1;}//我一开始写的二分法居然不知道是哪里出错了一个劲RE

}

printf("%d\n",ans);

}

} return 0;

}

2

(11,LL) (7,LLL) (8,R)(5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) ()(3,L) (4,R) ()

题目 意思参考 刘汝佳的那本算法入门经典

#include<stdio.h>

#include<malloc.h>

#include<string.h>

typedef struct haha

{

int num;

struct haha *left;

struct haha *right;

}node;

node *queue[300];

int ans[300];

int main()

{

int i,d,n,flag,head,tail,cnt,count;

node *root,*temp1,*temp2;

char s[10000];

while(scanf("%s",s)!=EOF)

{

flag=1;

d=strlen(s);

// puts(s);

if(d==2&&s[0]=='('&&s[1]==')') {printf("not complete\n");continue;}

root=(node *)malloc(sizeof(node));

root->left=NULL;root->right=NULL;

root->num=-1; temp1=root;

for(i=0;i<d;i++)

{

if(s[i]=='L')

{

temp2=(node *)malloc(sizeof(node));

temp2->num=-1;

temp2->right=temp2->left=NULL;

temp1->left=temp2;

temp1=temp2;

}

else if(s[i]=='R')

{

temp2=(node *)malloc(sizeof(node));

temp2->num=-1;

temp2->left=temp2->right=NULL;

temp1->right=temp2;

temp1=temp2;

}

}

if(s[1]==',') flag=0;

if(flag)

{

sscanf(s+1,"%d",&n);

if(temp1->num==-1)

{

temp1->num=n;

}

else flag=0;

}

cnt=1;

while(1)

{

scanf("%s",s);

cnt++;

d=strlen(s);

if(d==2&&s[0]=='('&&s[1]==')') break;

temp1=root;

if(flag)

for(i=0;i<d;i++)

的路不要重新建

{ if(s[i]=='L') { if(temp1->left!=NULL) temp1=temp1->left;//注意 已经建立起来 else { temp2=(node *)malloc(sizeof(node));; temp2->num=-1; temp2->right=temp2->left=NULL; temp1->left=temp2; temp1=temp2; } } else if(s[i]=='R') { if(temp1->right!=NULL) temp1=temp1->right; else { temp2=(node *)malloc(sizeof(node));; temp2->num=-1; temp2->left=temp2->right=NULL; temp1->right=temp2; temp1=temp2; } } } if(s[1]==',') flag=0; if(flag) { sscanf(s+1,"%d",&n); if(temp1->num==-1) { temp1->num=n; }

else flag=0;

}

}

// printf("why");

if(root->num==-1) flag=0;

head=1;tail=2;

queue[1]=root;count=0;

if(flag)

while(head<tail)

{

temp1=queue[head];

if(temp1->num!=-1) {ans[count++]=temp1->num;}

if(temp1->left!=NULL&&temp1->left->num!=-1)//还要保temp1->left->num!=-1 也就是说要找某个数 在找的路径中不能有没有赋值的路

queue[tail++]=temp1->left;

if(temp1->right!=NULL&&temp1->right->num!=-1)

queue[tail++]=temp1->right;

head++;

}

// printf("cnt=%d count=%d",cnt,count);

if(count==cnt-1&&flag)

{

for(i=0;i<count-1;i++)

printf("%d ",ans[i]);

printf("%d\n",ans[count-1]);

}

else printf("not complete\n");

}

return 0;

}

/*模拟建树 + BFS狂扫*/

3 证 畅通工程再续

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 6590 Accepted Submission(s): 1964

Problem Description

相信大家都听说一个“百岛湖”的地方吧，百岛湖的居民生活在不同的小岛中，当他们想去其他的小岛 时都要通过划小船来实现。现在政府决定大力发展百岛湖，发展首先要解决的问题当然是交通问题，政府决定实现百岛湖的全畅通！经过考察小组RPRush对百 岛湖的情况充分了解后，决定在符合条件的小岛间建上桥，所谓符合条件，就是2个小岛之间的距离不能小于10米，也不能大于1000米。当然，为了节省资 金，只要求实现任意2个小岛之间有

路通即可。其中桥的价格为 100元/米。

输入包括多组数据。输入首先包括一个整数T(T <= 200)，代表有T组数据。

每组数据首先是一个整数C(C <= 100),代表小岛的个数，接下来是C组坐标，代表每个小岛的坐标，这些坐标都是 0 <= x, y <= 1000的整数。

#include<stdio.h>

#include<math.h>

#include<stdlib.h>

struct haha

{

int view1;

int view2;

double value;

}e[10000+5];

int parent[10000+5];

int cmp(const void *a,const void *b)

{

return (*(struct haha *)a).value>(*(struct haha *)b).value?1:-1;

}

int get_root(int x)

{

return x==parent[x]?x:get_root(parent[x]);

}

int join(int x,int y)

{

int root1,root2;

root1=get_root(x);

root2=get_root(y);

if(root1==root2) return 0;

else

{

parent[root1]=root2;

}

return 1;

}

int main()

{

int t,i,j,a[105],b[105],n,k,cnt,flag;

double ans,mid;

scanf("%d",&t);

while(t--)

{

scanf("%d",&n);

parent[0]=0;

k=1;ans=0;cnt=0;

for(i=1;i<=n;i++)

scanf("%d %d",&a[i],&b[i]);

for(i=1;i<=n-1;i++)

for(j=i+1;j<=n;j++)

{

mid=(a[j]-a[i])*(a[j]-a[i])+(b[j]-b[i])*(b[j]-b[i]);

if(mid>=100&&mid<=1000000)

{

parent[k]=k;

e[k].view1=i;

e[k].view2=j;

e[k].value=sqrt(mid);

k++;

}

}

qsort(e+1,k-1,sizeof(e[0]),cmp);

for(i=1;i<=k;i++)

{

if(join(e[i].view1,e[i].view2))

{

cnt++;

ans=ans+e[i].value;

}

}

printf("%d\n",cnt);

if(cnt!=n-1) printf("oh!\n");

else

printf("%.1lf\n",ans*100.0);

}

return 0;

}

/*

假如共n个点 有些点之间联通 有些之间不联通 这时候假如一个包含已经连通的点的边 则二者root是相同的 该边不会加入 只有root不同的时候才会join 加入合并为一个树 此时cnt++ 如果有cnt==n-1 说明能找到n-1个边 即包含了n个点 即每个点之间都是连通的

*/

4 还是畅通工程

某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。

#include<stdio.h>

#include<stdlib.h>

struct haha

{

int view1;

int view2;

int value;

}e[10000+5];

int parent[10000+5],son[10000+5];

int cmp(const void *a,const void *b)

{

return (*(struct haha *)a).value-(*(struct haha *)b).value;//从小到大排序

}

int find_root(int x)//这个事找根的 跟满足root==parent[root] 其他不满足

{

return x==parent[x]?x:find_root(parent[x]);

}

int join(int x,int y)

{

int v2,v1;

v1=find_root(x);

v2=find_root(y);

// printf("v1=%d v2=%d\n",v1,v2);

if(v1==v2) return 0;//如果二者根相同 也就是说点v1到root有通路 v2到root也有通路 那么v1v2相连 则组成了环 所以不行

else//不相等 则是2颗树 相连

{

if(son[v1]>=son[v2])//这个地方我还没理解 不过把这些去掉 即把parent[v2]=v1;son[v1]+=son[v2];留下 把if(son[v1]>=son[v2])去掉 也AC

{

parent[v2]=v1;// 即else内只留下这2句 我想这个son数组就是用来使树以某种秩序进行建立

son[v1]+=son[v2];

}

else

{

parent[v1]=v2;

son[v2]+=son[v1];

}

}

return 1;

}

int main()

{

int n,i,k,cnt,flag,ans;

while(scanf("%d",&n)!=EOF)

{

cnt=0;flag=0;ans=0;

if(n==0) break;

for(i=1;i<n+5;i++)

{

parent[i]=i;//初始化 一开始每个点都是根

son[i]=1; //随便是几都无所谓

}

for(i=1;i<=n*(n-1)/2;i++)

{

scanf("%d %d %d",&e[i].view1,&e[i].view2,&e[i].value);

}

qsort(e+1,i-1,sizeof(e[0]),cmp);//注意是i-1个才对的

k=i;

for(i=1;i<k;i++)

{

if(join(e[i].view1,e[i].view2))

{

cnt++;

ans=ans+e[i].value;

if(cnt==n-1) flag=1;//找出n-1条就OK了

}

if(flag) break;

}

printf("%d\n",ans);

}

return 0;

}

题意是给你p个源字符串，然后询问Q个目的字符串，询问每个目的字符串时，要你从p个源字符串中找出包含目的字符串的个数。注意当第i个字符串中含有多个 目的字符串时，只当作一个。比如源串为ababab abcd 目的串为ab,则输出结果为2，而不是4.所以在建的时候要进行id的判断。此题在传统的建树上面作了变通：比如对字符串abcd进行建树时，不仅要对 abcd，还要对bcd,cd,d都进行建树，因为此题中的子串可能是开头，中间或者结尾，所以这样建有利于最后的询问，节省时间。

/*防止重复计算 例如：ababababc ab重复出现了好多次 建立ababababc ab出现了一次 建立abababc ab有出现了一次 建立ababc abc 均出现

这时候本来应该算作是一次的

那么当我们建立了ababababc 再次建立abababc的时候 我们前面要走相同的路线 那么这2

个子串是在同一个串中 所以次数就没必要增加了

所以用id标记是否属于同一个字符串 防止重复计算出现次数

#include<stdio.h>

#include<string.h>

#include<malloc.h>

struct haha

{

int cnt;

int id;//标记第几个字符串的 防止重复计算 防止重复出现某个串 比如ababababc ab重复出现了好多次

struct haha *next[26];

}*root;

int ans;

struct haha * creat()

{

int i;

struct haha *p;

p=(struct haha *)malloc(sizeof(struct haha));

p->cnt=1;

p->id=-1;

for(i=0;i<26;i++)

p->next[i]=NULL;

return p;

}

void update(char *s,int id)

{

int d,pos,i;

struct haha *p;

p=root;

d=strlen(s);

for(i=0;i<d;i++)

{

pos=s[i]-'a';

if(p->next[pos]==NULL)

{

p->next[pos]=creat();

p=p->next[pos];

p->id=id;

}

else

{

p=p->next[pos];

if(p->id!=id)//也就是说这个串的子串没有出现过

{

p->id=id;

p->cnt++;

}

}

}

}

void query(char *s)

{

struct haha *p;

int pos,i,d;

p=root;

d=strlen(s);

for(i=0;i<d;i++)

{

pos=s[i]-'a';

if(p->next[pos]==NULL) return ;

else

{

p=p->next[pos];

}

}

ans=p->cnt;

}

int main()

{

int i,n,m,k;

char s[30];

root=creat();

scanf("%d",&n);

for(k=0;k<n;k++)

{

scanf("%s",s);

for(i=0;s[i]!='\0';i++)

update(&s[i],k);

}

scanf("%d",&m);

while(m--)

{

ans=0;

scanf("%s",s);

query(s);

printf("%d\n",ans);

}

return 0;

}

真正求二分图的最大匹配的题目很少，往往做一些简单的变化：

变种1：二分图的最小顶点覆盖

最小顶点覆盖要求用最少的点（X或Y中都行），让每条边都至少和其中一个点关联。 knoig定理:二分图的最小顶点覆盖数 = 二分图的最大匹配数（m）。

变种2：DAG图的最小路径覆盖

用尽量少的不相交简单路径覆盖有向无环图(DAG)G的所有顶点，这就是DAG图的最小路径覆盖问题。

结论：DAG图的最小路径覆盖数 = 节点数（n）- 最大匹配数（m）

变种3:二分图的最大独立集

结论：二分图的最大独立集数 = 节点数（n）— 最大匹配数（m）

最大独立集相当于问：在Ｎ个点的图G中选出m个点，使这m个点两两之间没有边．求m最大值

当我们遇到的题目中可以将数据分成2个集合的时候就应该敏感性的想到二分匹配 //Cat VS Dog.cpp : 定义控制台应用程序的入口点。

//

/*

题目描述：动物园有N只猫，M只狗，P个小孩。每个小孩都有自己喜欢的动物和讨厌的动物，如果他喜欢狗，那么就讨厌猫，

如果他讨厌猫，那么他就喜欢狗。某个小孩能开心，当且仅当他喜欢的动物留在动物园和讨厌的动物不在动物园里面。

现让管理员通过带走某些动物，问最多能使多少个孩子开心。

解题思路：题目有一个关键点，孩子喜欢猫，必然不喜欢狗，反之。 即猫和猫之间，狗和狗之间一定不存在矛盾关系，符合二分图的概念。

如何建立二分图：

若甲小孩喜欢的动物与乙小孩讨厌的动物一样，或者甲小孩讨厌的动物与乙小孩喜欢的动物一样，那甲乙之间就存在着排斥关系，则他们之间连接一条边。

建立完二分图之后，相当于求二分图的最大独立集 = 顶点数 - 最大匹配数。

*/

#include "stdafx.h"

#include <iostream>

#include <cstring>

#include <string>

#include <algorithm>

using namespace std;

const int MAXN = 508;

struct Child

{

string like;

string dis;

};

Child cat[MAXN],dog[MAXN];

int map[MAXN][MAXN];

int link[MAXN];

int used[MAXN];

int cat_num;

int dog_num;

int dfs(int k)

{

for(int i=0; i<dog_num; i++)

{

if(!used[i] && map[k][i])

{

used[i] = 1;

if(link[i] == -1 || dfs(link[i]))

{

link[i] = k;

return 1;

}

}

}

return 0;

}

int maxMatch()

{

int cnt = 0;

for(int i=0; i<cat_num; i++)

{

memset(used,0,sizeof(used));

if(dfs(i))

{

cnt++;

}

}

return cnt;

}

int main()

{

}

string a,b; while(cin>>n>>m>>p) { memset(map,0,sizeof(map)); memset(link,-1,sizeof(link)); cat_num = dog_num = 0; while(p--) { cin>>a>>b; //将喜欢猫的孩子划为A子集 if(a[0] == 'C') { cat[cat_num].like = a; cat[cat_num].dis = b; cat_num++; } //将喜欢狗的孩子划为B子集 if(a[0] == 'D') { dog[dog_num].like = a; dog[dog_num].dis = b; dog_num++; } } for(int i=0; i<cat_num; i++) { for(int j=0; j<dog_num; j++) { //若存在排斥关系 if(cat[i].like == dog[j].dis || cat[i].dis == dog[j].like) { map[i][j] = 1; } } } int cnt = maxMatch(); //最大独立集 = 顶点数 - 最大匹配数 cout<<cat_num+dog_num-cnt<<endl; } return 0;

题意：n个同学，一些男女同学会有缘分成为情侣，格式ni:(m) n1 n2 n3表示同学ni有缘与n1,n2,n3成为情侣，求集合中不存在有缘成为情侣的同学的最大同学数。

题解：

独立集：图的顶点集的子集，其中任意两点不相邻

最大独立集 = 顶点数 - 最大匹配数

但是这道题有一点不同，它没有告诉我们是男生还是女生，所以我们需要进行拆点，把一个学生拆成一个男生和一个女生，然后求出最大匹配后除以2即可。

*/

#include <iostream>

using namespace std;

const int nMax = 500;

int n;

int map[nMax][nMax];

int link[nMax];

int useif[nMax];

bool can(int t)

{

for(int i = 0; i < n; ++ i)

{

if(!useif[i] && map[t][i])

{

useif[i] = 1;

if(link[i] == -1 || can(link[i]))

{

link[i] = t;

return 1;

}

}

}

return 0;

}

int main()

{

//freopen("f://data.in", "r", stdin);

while(scanf("%d", &n) != EOF)

{

memset(map, 0, sizeof(map));

memset(link, -1, sizeof(link));

int u, k, v;

for(int i = 0; i < n; ++ i)

{

scanf("%d: (%d)", &u, &k);

while(k --)

{

scanf("%d", &v);

map[u][v] = 1;

}

}

int num = 0;

for(int i = 0; i < n; ++ i)

{

memset(useif, 0, sizeof(useif));

if(can(i)) ++ num;

}

printf("%d\n", n - num / 2);

}

return 0;

}

最小路径覆盖

路径覆盖的定义是：在有向图中找一些路径，使之覆盖了图中的所有顶点，就是任意一个顶点都跟那些路径中的某一条相关联，且任何一个顶点有且只有一条路径与之关联，一个单独的顶点是一条路径.最小路径覆盖就是最少的路径覆盖

注意：每个点的入度出度都是1 也就是说 每个点决定1条边

poj 1422

题意：一个地图上有n个小镇，以及连接着其中两个小镇的有向边，而且这些边无法形成回路。现在选择一些小镇空降士兵（1个小镇最多1个士兵），士兵能沿着边走到尽头，问最少空降几个士兵，能遍历完所有的小镇。

思路：匈牙利算法求最小路径覆盖：在一个有向图中，路径覆盖就是在图中找一些路径，使之覆盖了图中的所有顶点，且任何一个顶点有且只有一条路径与之关联； （如果把这些路径中的每条路径从它的起始点走到它的终点，那么恰好可以经过图中的每个顶点一次且仅一次）；解决此类问题可以建立一个二分图模型。把所有顶 点i拆成两个：Ｘ结点集中的i和Y结点集中的i',如果有边i->j，则在二分图中引入边i->j'，设二分图最大匹配为m,则结果就是n- m

用二分图来做

对于这样的一个有向图做最小路径覆盖，首先建图

先拆点，将每个点分为两个点，左边是1到n个点，右边是1-n个点 然后每一条有向边对应左边的点指向右边的点

这样建好图之后求最大匹配数

因为最小路径覆盖=点数-最大匹配数

/*

*/

#include<iostream>

using namespace std;

#define MAXV 130

int n,m; //交叉路口和街道的个数

int map[MAXV][MAXV];

int link[MAXV],use[MAXV];

bool dfs(int x){

int i,j;

for(i=1;i<=n;i++){

if(map[x][i] && !use[i] ){ //拆点注意i不能等于x，否则就自己和自己匹配了

j=link[i];

use[i]=1;

link[i]=x;

if(j==-1 || dfs(j)) return true;

link[i]=j;

}

}

return false;

}

int hungary(){

int num=0;

int i;

memset(link,-1,sizeof(link));

for(i=1;i<=n;i++){

memset(use,0,sizeof(use));

if(dfs(i)) num++;

}

return n-num;

}

int main(){

int Case;

int a,b,i;

scanf("%d",&Case);

while(Case--){

scanf("%d%d",&n,&m);

memset(map,0,sizeof(map));

for(i=0;i<m;i++){

scanf("%d%d",&a,&b);

map[a][b]=1;

}

printf("%d\n",hungary());

}

return 0;

}\

/*题目大意：在一个坐标图中有一些点需要覆盖，每在一个点上覆盖就可在覆盖它上下左右4个点中任一个，问最小放几个。

分析：利用黑白染色法把每一个点都和与之相邻的4个点连边，就构成了一个二分图。要求的就是有最小的点数覆盖全部边，即求最小路径覆盖=最大独立集=所有点-最大匹配由此可以求出最优解。实现方法——匈牙利算法即可。注意的是，这里的点是所有可以放得点*2，而匹配数也是正常匹配数的二倍（A到B连了，B到A也连了），所以最后是n-最大匹配/2。

代码：

*/

#include<iostream>

using namespace std;

int h[41][11];

int g[405][405],visit[405],match[405];

char map[41][11];

int d[4][2]={{-1,0},{1,0},{0,-1},{0,1}};

int n,m,ans,sum;

int find(int a)

{

int i,j;

for(i=1;i<=sum;i++)

{

if(!visit[i]&&g[a][i]==1)

{

visit[i]=1;

if(match[i]==0||find(match[i]))

{

match[i]=a;

return 1;

}

}

}

return 0;

}

int main()

{

int t,i,j,k,xx,yy;

cin>>t;

while(t--)

{

sum=ans=0;

memset(g,0,sizeof(g));

memset(match,0,sizeof(match));

cin>>n>>m;

for(i=0;i<n;i++)

{

cin>>map[i];

for(j=0;j<m;j++)

{

if(map[i][j]=='*')

{

sum++;

h[i][j]=sum;

}

}

}

for(i=0;i<n;i++)

for(j=0;j<m;j++)

{

if(map[i][j]=='*')

{

for(k=0;k<=3;k++)

{

xx=i+d[k][0];

yy=j+d[k][1];

if(xx>=0&&yy>=0&&xx<n&&yy<m&&map[xx][yy]=='*')

g[h[i][j]][h[xx][yy]]=1;

}

}

}

for(i=1;i<=sum;i++)

{

memset(visit,0,sizeof(visit));

if(find(i)) ans++;

}

cout<<sum-ans/2<<endl;

}

return 0;

}

题目大意：给出N（1000）个数字（<2^63 -1），从n中取出k个数，使得任意a，b属于k，a，b不形成整除关系。问k最大是多少

算法：有向图最小路径覆盖数

思路：因为要求取出一些点，使得他们之间没有整除关系，很容易想到利用整除关系建立一个图，然后看最多有多少个点能不相连，如果把图看作无向图，那么就很难想到做法，至少无向图最大点独立集是不能在1000的规模下运行的。如果a是b的约束，我们建立一条a向b的有向边，最后发现，要求的其实就是最小路径覆盖数。

最小路径覆盖数：在一个有向图中至少放几个人才能走到所有点（延边走，人可以放在任意位置，非官方解释）。

最小路径覆盖：在一个有向图中，最少用几条路径能把所有的点覆盖（路径不交叉，即每个点只属于一条路）。

当有向图无环时，可以用二分图最大匹配来求解。

最少路径覆盖=点数–二分图最大匹配

代码略

本文来源：https://www.bwwdw.com/article/fkhj.html