BZOJ1083:|BZOJ1083: [SCOI2005]繁忙的都市
题意
给定一张图,求其最小生成树中权值最大的边
要是学习过最小生成树的相关概念,就会发现这道题就是直接考察的最小生成树,只不过题目没有问你最小生成树的边权和,而是让你输出最小生成树有几条边(点数-1)和权值最大的那条边的权值。
那么什么是生成树呢?
In the mathematical field of graph theory, a spanning tree T of an undirected graph G is a subgraph that is a tree which includes all of the vertices of G. In general, a graph may have several spanning trees, but a graph that is not connected will not contain a spanning tree (but see Spanning forests below). If all of the edges of G are also edges of a spanning tree T of G, then G is a tree and is identical to T (that is, a tree has a unique spanning tree and it is itself).
文章图片
如上图所示,生成树就是在给定的图中选取最少的边使所有顶点连通,那么最小生成树就是选取的边的权值和最小。
了解了生成树的概念,就很容易能明白生成树只有n-1条边,其中n表示顶点数。
那么怎么求最小生成树呢?
这里我介绍kruscal算法。
克鲁斯卡尔算法
该算法用到的是贪心思想,将所有的边按权值排序,每次都选权值最小的边,然后判断这条边的两个顶点是否属于同一个连通块,如果不属于同一个连通块,那么这条边就应属于最小生成树,逐渐进行下去,直到连通块只剩下一个。
kruscal算法的模板代码如下:
const int maxn=400;
//最大点数
const int maxm=10000;
//最大边数
int n,m;
//n表示点数,m表示边数
struct edge{int u,v,w;
} e[maxm];
//u,v,w分别表示该边的两个顶点和权值
bool cmp(edge a,edge b)
{
return a.w
【BZOJ1083:|BZOJ1083: [SCOI2005]繁忙的都市】针对这道题,我们只需要把ans+=e[i].w改为ans=max(ans,e[i].w)就好了,至此问题得到了解决。
#include
#include
#include
#include
using namespace std;
const int maxn=400;
const int maxm=10000;
int n,m;
struct edge{int u,v,w;
} e[maxm];
bool cmp(edge a,edge b)
{
return a.w>n>>m;
for(int i=1;
i<=m;
++i) cin>>e[i].u>>e[i].v>>e[i].w;
cout<
推荐阅读
- 任时光绽放成六月繁花
- 那条灰色的人行道
- 繁华声遁入空门
- 愿你的生活从此不将就
- 监考与阅读
- 夜空繁星,你看得清哪一颗
- 旱季燕窝与雨季燕窝的区别
- 看当下,盛世繁花
- 一场与繁华和浪漫交织的邂逅
- 《繁凡的深度学习笔记》|一文绝对让你完全弄懂信息熵、相对熵、交叉熵的意义《繁凡的深度学习笔记》第 3 章 分类问题与信息论基础(中)(DL笔记整理