思路:kruskal + 枚举生成树
分析:题目要求的是找到一个生成树使得生成树中“最大边-最小边”的值最小。如果这个图有n个点,那么这个生成树有n-1条边。那么现在就是考虑怎么去枚举这些生成树,我们想到了跟边有关的就是kruskal。我们只要按照边的大小排好序,然后去枚举最小的边的值,因为每一个生成树都要有n-1条边,所以只要枚举从0~(m-n+1)即可,然后按照求解最小生成树的方法去求每一个生成树,最后求出ans。
代码:
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> using namespace std; #define MAXN 10000 #define INF 0xFFFFFFF int n , m , flag; int father[MAXN]; int rank[MAXN]; struct Edge{ int x; int y; int value; }e[MAXN]; /*排序*/ bool cmp(Edge e1 , Edge e2){ return e1.value < e2.value; } /*并查集的初始化*/ void init_Set(){ for(int i = 1 ; i <= n ; i++){ father[i] = i; rank[i] = 0; } } /*并查集的查找*/ int find_Set(int x){ if(x != father[x]) father[x] = find_Set(father[x]); return father[x]; } /*并查集的合并*/ void union_Set(int x , int y){ if(rank[x] > rank[y]) father[y] = x; else{ if(rank[x] == rank[y]) rank[y]++; father[x] = y; } } /*判断当前的生成树是否合法*/ bool judge(){ int root = find_Set(1); for(int i = 2 ; i <= n ; i++){ if(find_Set(i) != root) return false; } return true; } /*kruskal的算法*/ void kruskal(){ int ans = INF; int min , max; sort(e , e+m ,cmp); for(int i = 0 ; i <= (m-n+1) ; i++){ init_Set();/*每一次都进行初始化*/ min = INF;/*初始化最小值边*/ max = 0;/*初始化最大值的边*/ for(int j = i ; j < m ; j++){ int root_x = find_Set(e[j].x); int root_y = find_Set(e[j].y); if(root_x != root_y){ union_Set(root_x , root_y); if(min > e[j].value) min = e[j].value; if(max < e[j].value) max = e[j].value; } } if(judge()){/*如果是一个合法的生成树*/ flag = 1; ans = ans < (max-min) ? ans : (max-min);/*更新ans*/ } } if(flag) printf("%d\n" , ans); else printf("-1\n"); } int main(){ while(scanf("%d%d" , &n , &m) &&n+m){ flag = 0; for(int i = 0 ; i < m ; i++) scanf("%d%d%d" , &e[i].x , &e[i].y , &e[i].value); kruskal(); } return 0; }