【c++ 图论例题学习】【口袋的天空】【部落划分】

作者：贤鱼很忙

2022-10-26
新疆
本文字数：2349 字
阅读完需：约 8 分钟

目标：

今天的两道题做法和思路有相同之处，合并在一起学习可以帮助更快的掌握图论中克鲁斯卡尔算法的要点和据具体实现步骤，下面来看看题目：

第一题【口袋的天空】

题目如下题目背景小杉坐在教室里，透过口袋一样的窗户看口袋一样的天空。

有很多云飘在那里，看起来很漂亮，小杉想摘下那样美的几朵云，做成棉花糖。

题目描述给你云朵的个数 N，再给你 M 个关系，表示哪些云朵可以连在一起。

现在小杉要把所有云朵连成 K 个棉花糖，一个棉花糖最少要用掉一朵云，小杉想知道他怎么连，花费的代价最小。

输入格式第一行有三个数 N,M,K。

接下来 M 行每行三个数 X,Y,L 表示 X 云和 Y 云可以通过 L 的代价连在一起。

输出格式对每组数据输出一行，仅有一个整数，表示最小的代价。

如果怎么连都连不出 K 个棉花糖，请输出 No Answer。

输入输出样例输入 #1 复制 3 1 21 2 1 输出 #1 复制 1 说明/提示对于 30% 的数据，1≤N≤100,1≤M≤10 ^3

对于 100%100% 的数据，1≤N≤10^3，1≤M≤10 ^4，1≤K≤10，1≤X,Y≤N，0≤L<10^4

思路：

由于题目中说需要连接出 k 个棉花糖，所以在处理数据的时候特判一下，记录下输入内容然后克鲁斯卡尔算法进行处理，因为有 n 个云，要连成 k 个棉花糖，所以当边数等于 n-k 是结束程序即可。

代码实现:

#include<algorithm>#include<cstdio>#include<cstring>#include<iostream>#include<cmath>using namespace std;int n,m,k;struct edge{  int u,v,w;  bool operator <(const edge &a)const{    return w<a.w;//将结构体中的权值作为排序对象处理  }}e[1010101];int f[1000001];int ecnt=0;void add(int u,int v,int w){  e[++ecnt].u=u;  e[ecnt].v=v;  e[ecnt].w=w;}int getf(int x){  return x==f[x]?x:f[x]=getf(f[x]);//寻找共同的起点}int main(){  cin>>n>>m>>k;  for(int i=1;i<=m;i++){    int a,b,c;    cin>>a>>b>>c;    add(a,b,c);//记录数据  }  for(int i=1;i<=n;i++){    f[i]=i;//初始化，让每个点的起点都为每个点本身  }  int cnt=0,w=0;  sort(e+1,e+1+ecnt);  //克鲁斯卡尔算法处理  for(int i=1;i<=ecnt;i++){    int u=getf(e[i].u);    int v=getf(e[i].v);    if(u!=v){//当两个点没有共同起点的时候，进行加边处理      cnt++;//增加边数      w+=e[i].w;//记录答案      f[u]=v;//同步起点    }    if(cnt==n-k){//当cnt等于n-k时说明满足题意      cout<<w;      return 0;    }  }  cout<<"No Answer";}

复制代码

第二题【部落划分】

题目如下

题目描述聪聪研究发现，荒岛野人总是过着群居的生活，但是，并不是整个荒岛上的所有野人都属于同一个部落，野人们总是拉帮结派形成属于自己的部落，不同的部落之间则经常发生争斗。只是，这一切都成为谜团了——聪聪根本就不知道部落究竟是如何分布的。

不过好消息是，聪聪得到了一份荒岛的地图。地图上标注了 n 个野人居住的地点（可以看作是平面上的坐标）。我们知道，同一个部落的野人总是生活在附近。我们把两个部落的距离，定义为部落中距离最近的那两个居住点的距离。聪聪还获得了一个有意义的信息——这些野人总共被分为了 k 个部落！这真是个好消息。聪聪希望从这些信息里挖掘出所有部落的详细信息。他正在尝试这样一种算法：

对于任意一种部落划分的方法，都能够求出两个部落之间的距离，聪聪希望求出一种部落划分的方法，使靠得最近的两个部落尽可能远离。

例如，下面的左图表示了一个好的划分，而右图则不是。请你编程帮助聪聪解决这个难题。

输入格式输入文件第一行包含两个整数 n 和 k，分别代表了野人居住点的数量和部落的数量。

接下来 n 行，每行包含两个整数 x，y，描述了一个居住点的坐标。

输出格式输出一行一个实数，为最优划分时，最近的两个部落的距离，精确到小数点后两位。

输入输出样例输入 #1 复制 4 20 00 11 11 0 输出 #1 复制 1.00 输入 #2 复制 9 32 22 33 23 33 53 64 66 26 3 输出 #2 复制 2.00 说明/提示数据规模与约定对于 100%100% 的数据，保证 2≤k≤n≤10^3，0≤x,y≤10^4

思路如下：

和上一题大部分做法一样，但是需要注意题目中的不同之处，本题的 cnt 需要等于 n-k+1 时结束。具体原因请仔细读题

代码实现：

#include<cmath>#include<cstdio>#include<cstring>#include<algorithm>#include<iostream>using namespace std;int f[10005];int ecnt=0;int cnt=0;int n,k;struct edge{  int u,v;  int w;  bool operator <(const edge &s)const{    return w<s.w;  }}e[1001010];void add(int u,int v,int w){  e[++ecnt].u=u;  e[ecnt].w=w;  e[ecnt].v=v;}double w=0;
int ax[101010],ay[100005];int  js(int x,int y){  return (ax[x]-ax[y])*(ax[x]-ax[y])+(ay[x]-ay[y])*(ay[x]-ay[y]);//在此先不进行开方运算，下文统计答案时会开方}int getf(int x){  return x==f[x]?x:f[x]=getf(f[x]);}int main(){  cin>>n>>k;  for(int i=1;i<=n;i++){    cin>>ax[i]>>ay[i];//此题给的是点的坐标所以需要先存下来    }    for(int i=1;i<n;i++){    for(int j=i+1;j<=n;j++){      add(i,j,js(i,j));//函数计算每个点的距离    }  }  for(int i=1;i<=n;i++){    f[i]=i;  }  sort(e+1,e+1+ecnt);  //开始处理  for(int i=1;i<=ecnt;i++){    int u=getf(e[i].u);    int v=getf(e[i].v);    if(u!=v){      cnt++;      f[u]=v;      w=sqrt(e[i].w);//注意数据类型      if(cnt==n-k+1){//注意题目要求                printf("%.2lf",w);//注意输出格式        return 0;      }    }  }  }

复制代码

总结如下：

这两道题大体上相似之处较多，但是需要注意题目细节和要求，对于不同的数据和要求需要稍加改动，这两道题可以帮助更加深刻的记忆和了解克鲁斯卡尔算法的过程和实现。

发布于: 刚刚阅读数: 4

原文链接:【http://xie.infoq.cn/article/ba906ed63c92819dabc8a15a7】。未经作者许可，禁止转载。

贤鱼很忙

关注

为了未来奋斗中 2022-09-28 加入

主修网络安全和c++方面内容，时常提供题解和网络安全方面知识

发布

暂无评论

创作场景