题解 P1547 【Out of Hay】

### 题目：out of hay（翻译：奶牛爱干草） （花里胡哨的 没有用） [题目传送门](https://www.luogu.org/problemnew/show/P1547) 本人身为蒟蒻 来水一篇题解 题目还是好水的，最重要的是，题目把最主要的算法直接说出来了（真是直接啊） ------------------------------------------------------------**分割线**--------------------------------------------------------- 最小生成树： 就是任意一棵最小生成树一定包含无向图中权值最小的边。 这里有Kruskal和Prim两种算法 个人推荐克鲁斯卡尔（稀疏图） ##### 算法流程如下： ##### 1.建立一个并查集，每个点各自构成一个集合。 ##### 2.把所有边按照权值从小到大排序，依次扫描每条边 ##### 3.若x，y连通，就忽略这条边，扫描下一条 ##### 4.否则，合并x，y所在的集合，并把z累加到答案里 时间复杂度为**O(m log m)** 下面上代码（想说的在里头） ```c #include<iostream> #include<algorithm> using namespace std; int n,m; long long fa[100000001]; struct hay { int x,y,z; }a[10001]; inline bool cmp(hay a,hay b) { return a.z<b.z; } //将权值从小到大排序 inline int find(int t) { if(fa[t]==t) return t; else return fa[t]=find(fa[t]); } //路径压缩的日常。。。。 inline void me(int r1,int r2) { int s1=find(r1); int s2=find(r2); fa[s1]=s2; } // 核心代码如下 inline void Kruskal() { int k=0; int k1,k2; int ans=0; for(int i=1;i<=m;i++) { k1=find(a[i].x); k2=find(a[i].y); if(k1==k2) continue;//如果在一个集合内就忽略这条边，扫描下一条 k++; me(k1,k2); //合并 x y所在的集合 就是把边（x，y）放入最小生成树中 ans=max(a[i].z,ans); if(k==n-1) break; //到n-1条边停止，最小生成树只需要n-1条边 } cout<<ans; } int main() { cin>>n>>m; int i; for(i=1;i<=n;i++) { fa[i]=i; } //并茶集初始化 //所有元素各自构成一个独立的集合 即为n棵点数为1的树 for(i=1;i<=m;i++) { cin>>a[i].x>>a[i].y>>a[i].z; } sort(a+1,a+m+1,cmp); Kruskal(); return 0; } ``` # 制作不易 不喜勿喷