2018 UESTC 图论培训B课程有哪些内容？

本文共计797个文字，预计阅读时间需要4分钟。

B+-+天才金钱vs学霸周+大概念意：设定顶点和具有权重的边，求问最小生成树是否唯一。+思路分析：找出组成最小生成树所需的最少边数，以及可以构成最小生成树的边数，二者进行比较即可。“

B - 天才钱vs学霸周
大概题意：给定顶点和带有权值的边，求问最小生成树是否唯一。

思路分析：找出组成最小生成树需要的边数，以及可以构成最小生成树的边数，二者进行比较即可。

核心代码：
1.

结构体 node 记录边的相关信息。而 find 自然就是并查集的了，还有就是比较边的权值大小。
2.

Kruskal 算法。首先将每一个节点都设置为自己的根节点，其次就是将所有的边按权值大小进行排列。由于是找到最小生成树，那么遍历一遍即可。首先的 cnt1 是用来记录相同权值而且可以构成最小生成树的边数，注意如果不是同一个根节点，那么就记录下来；第二个则是找最小生成树的了，cnt2 用来记录最小生成树的边，其中的 pre[ u ]= v ，是将前驱节点改变，因为是加入到树中，如果 cnt2 == n-1 的话，就可以直接退出了。那么最后比较一下，如果最小生成树不唯一，那么 输出 zin ；相反就输出 ogisosetsuna 。
以上整个题目就得以解决啦！ 其实我刚开始是准备把所有最小生成树的个数都找到，然后再与1 进行比较，但看起来貌似还是并查集比较好写。

#include<bits/stdc++.h> using namespace std; typedef long long ll; #define maxn 2000005 struct node { int u,v; ll w; }g[maxn]; int n,m; int pre[2003]; int find(int x) { return x==pre[x]?x:pre[x]=find(pre[x]); } bool cmp(const node &x,const node &y) { return x.w<y.w; } void kruskal() { int cnt1=0; int cnt2=0; for(int i=1;i<=n;i++)pre[i]=i; sort(g,g+m,cmp); for(int i=0;i<m;){ int j=i; while(j<m&&g[j].w==g[i].w){ int u=find(g[j].u); int v=find(g[j].v); if(u!=v){ cnt1++; } j++; } j=i; while(j<m&&g[j].w==g[i].w){ int u=find(g[j].u); int v=find(g[j].v); if(u!=v){ cnt2++; pre[u]=v; } j++; } i=j; if(cnt2==n-1)break; } if(cnt1>cnt2)printf("zin\n"); else printf("ogisosetsuna\n"); } int main() { scanf("%d%d",&n,&m); int a,b; ll ww; for(int i=0;i<m;i++){ scanf("%d%d%lld",&a,&b,&ww); g[i].u=a; g[i].v=b; g[i].w=ww; } kruskal(); return 0; }