1.上午（2h）
或者看最小生成树的视频和博客
从下午到晚上(6)h）
1.刷出三道题。
2.模板题有两种方法
题目描述
例如，给出一个无向图，找出最小生成树。如果图不连接，则输出orz。
输入格式
第一行包含两个整数N,MN,M，表示图共有NN个结点和MM条无向边。
接下来MM每行包含三个整数X_i,Y_i,Z_iXi,Yi,Zi，这意味着有一个长度Z_iZi无向边连接点X_i,Y_iXi,Yi。
输出格式
如果图片连接，则输出一个整数表示生成树的最小长度之和。如果图片不连接，则输出orz。
输入输出样例
复制
4 5 1 2 2 1 3 2 1 4 3 2 3 4 3 4 3
复制
7
说明/提示
数据规模：
对于20\ %的数据，N\le 5N≤5，M\le 20M≤20。
对于40\@%的数据，N\le 50N≤50，M\le 2500M≤2500。
对于70\p%的数据，N\le 500N≤500，M\le 10^4M≤104。
对于100\0%的数据：1\le N\le 50001≤N≤5000，1\le M\le 2\times 10^51≤M≤2×105，1\le Z_i \le 10^41≤Zi≤104。
样例解释：
因此，最小生成树的总边权是2 2 3=72 2 3=7。
方法一:Prim
#include<bits/stdc .h> using namespace std; #define inf 123456789 #define maxn 5005 #define maxm 200005 int head[maxn],dis[maxn],cnt,tot,n,m,now=1,ans=0; bool vis[maxn]; struct node{ int s; int e; int next; }e[maxm]; void add(int a,int b,int c)//前向星 { cnt ; e[cnt].s=b; e[cnt].e=c; e[cnt].next=head[a]; head[a]=cnt; } int prim() { for(int i=2;i<=n;i )//初始化为最大 { dis[i]=inf; } for(int i=head[1];i;i=e[i].next)//更新 { dis[e[i].s]=min(dis[e[i].s],e[i].e); } while( tot<n) { int minn=inf; vis[now]=1; for(int i=1;i<=n;i ) { if(!vis[i]&&minn>dis[i])////此时更改点连接找到最小点 { minn=dis[i]; now=i; } } ans =minn; for(int i=head[now];i;i=e[i].next) { int k=e[i].s; if(dis[k]>e[i].e&&!vis[k]) { dis[k]=e[i].e; } } } return ans; } int main() { cin>>n>>m; for(int i=1;i<=m;i ) { int a,b,c; cin>>a>>b>>c; add(a,b,c);//双向 add(b,a,c); } printf("%d",prim()); } 方法二：并收集，kruskal
#include<iostream> #include<algorithm> using namespace std; int p[5005] struct node { int a,b,v; }mp[500000]; bool cmp(node a,node b)//排序 { return a.v<b.v; } int find(int x)//找祖宗 { int r=x; while(p[r]!=r&&p[r]!=0) r=p[r]; return p[x]=r; } int kruskal(int n,int m)//类似于贪婪 { int ans=0,cnt=0; sort(mp 1,mp 1 m,cmp); for(int i=1;i<=m;i ) { int x=find(mp[i].a); int y=find(mp[i].b); if(x==y)//判断是否成环 continue; ans =mp[i].v; p[x]=y; if( cnt==n-1) break; } for(int i=1;i<n;i ) if(find(i)!=find(i 1))ans=0; return ans; } int main() { int n,m,a,b,v; cin>>n>>m; for(int i=1;i<=m;i ) { cin>>a>>b>>v; mp[i].a=a; mp[i].b=b; mp[i].v=v; } int ans=kruskal(n,m); if(ans) cout<<ans; else cout<<"orz"; return 0; }