傳送門? ? ?練習

只是一個最小生成樹的水題，拿來練練模板

AC代碼：

#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> using namespace std; #define maxn 10001 struct hh {int x,y,z; }t[maxn]; int n,m,fa[maxn],ans=0,bj,jl[maxn],top=0; bool cmp(const hh&x,const hh&y) {return x.z<y.z; } inline int find(int u) {if(fa[u]==u) return u;fa[u]=find(fa[u]);return u=fa[u]; } inline void kruskal() {int f1,f2,k,i;k=0;for(i=1;i<=n;i++) fa[i]=i;//初始化for(i=1;i<=m;i++){f1=find(t[i].x);f2=find(t[i].y);if(f1!=f2){ans=ans+t[i].z;jl[++top]=t[i].z;fa[f1]=f2;k++;if(k==n-1) break;}} } int main() {cin>>n>>m;ans=0;bj=1;for(int i=1;i<=m;i++){cin>>t[i].x>>t[i].y>>t[i].z;}sort(t+1,t+m+1,cmp);kruskal();sort(jl+1,jl+top);cout<<jl[top]<<endl; return 0; }

再附上最小生成樹純模板：

#include<bits/stdc++.h> using namespace std; const int maxn=200005; struct edge{int x,y,z;}a[maxn];//定義數組（好用的結構體） int n,m,fa[maxn],ans=0,bj; bool cmp(const edge&x,const edge&y)//重定義sort函數（背模板吧。。） {return x.z<y.z; } int find(int u)//查找祖先 {if(fa[u]==u) return fa[u];fa[u]=find(fa[u]);return fa[u]; } void kruskal()//kruskal的核心程序 {int f1,f2,k,i;k=0;for(i=1;i<=n;i++) fa[i]=i;for(i=1;i<=m;i++) {f1=find(a[i].x);f2=find(a[i].y);//并查集基本操作 if(f1!=f2)//兩點之間沒有邊（有邊就不管） {ans=ans+a[i].z;fa[f1]=f2;k++;//搭邊并記錄 if(k==n-1) break;//圖剛好為最小生成樹，退出 }}if(k<n-1){cout<<"orz"<<endl;bj=0;return;}//邊數達不到最小生成樹要求 } int main() {cin>>n>>m;//輸入點數，邊數 ans=0;bj=1;//ans記錄總的邊權長，bj判斷能否組成最小生成樹 for(int i=1;i<=m;i++){cin>>a[i].x>>a[i].y>>a[i].z;//輸入點1，點2，并賦上權值 }sort(a+1,a+m+1,cmp);//從小到大排序 kruskal();//建樹 if(bj) cout<<ans<<endl;//有最小生成樹就輸出ans return 0; }

?

轉載于:https://www.cnblogs.com/lck-lck/p/9571610.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的P1547 Out of Hay的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。