题解 P1547 【Out of Hay】

**最小生成树算法** ~~根据题目描述，这道题是最小生成树~~ **树**： ~~树是一种植物，木本植物之总名，主要由根、干、枝、叶、花、果组成~~ 一个不存在回路的无向联通图叫做树 **生成树**：生成树是连通图的极小联通子图。（加边会出现回路，减边变为非连通图） **最小生成树**： 生成树的各边权值总和最小的树（最小代价树） 最小生成树一般有两种算法：prim和kruskal。prim一般用于稠密图，kruskal用于稀疏图。 这里介绍一下kruskal。 kruskal算法的基本思想是：始终选择当前可用的最小权值边（贪心 因此很容易想到题目所求的最大边就是最后一条边（每次加边权取max也可以）。 那么怎么判断当前选择的边是否可用呢？ **并查集** 意思就是说，开始的每个点都是独立的集合，加边的时候就合并起来，如果已经是联通的就跳过。 附上代码``` ```c #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int fa[200004]; int n,m,l,r,tot,ans,k; inline int read(){ int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1; ch=getchar(); } while(ch>='0'&&ch<='9'){ x=x*10+ch-'0'; ch=getchar(); } return x*f; }//快读 struct node{ int fir;//第一个点 int sec;//第二个点 int data;//边权 }edge[400005]; inline int find(int x){ if(x==fa[x])return x; else return fa[x]=find(fa[x]); } inline bool cmp(node a,node b){ return a.data<b.data;//结构体排序 } inline void kruskal(){ for(register int i=1;i<=m;i++){ l=find(edge[i].fir); r=find(edge[i].sec); if(l==r)continue ;//如果联通就跳过 fa[l]=r;//否则就合并 k=edge[i].data;//每次更新边权，最后一条边为最大 // maxn=max(maxn,edge[i].data);每次加边取max也可以 tot++; if(tot==n-1)break; } } int main(){ n=read(); m=read(); for(register int i=1;i<=n;i++) fa[i]=i;//初始化并查集 for(register int i=1;i<=m;i++){ edge[i].fir=read(); edge[i].sec=read(); edge[i].data=read(); } sort(edge+1,edge+m+1,cmp);//将边权排序，每次加小的 kruskal(); cout<<k;//我喜欢cout... return 0; } ``` ```