首页 > 代码库 > 2017 Training for Graph Theory
2017 Training for Graph Theory
给你一个有nn个点和mm条边的无向连通图,每条边都有一个权值ww.我们定义，对于一条路径，它的Charm valueCharm value为该路径上所有边的权值的最大值与最小值的差.询问从11到nn的所有路径的Charm valueCharm value的最小值.
Input
第一行有两个整数n,m(1≤n≤200,n−1≤m≤1000)n,m(1≤n≤200,n−1≤m≤1000)，表示该图有nn个点和mm条边.接下来mm行，每行三个整数u,v,w(1≤u,v≤n,1≤w≤1000000)u,v,w(1≤u,v≤n,1≤w≤1000000)，表示点uu和点vv之间有一条权值为ww的边.
Output
输出一个数，即从11到nn的所有路径的Charm valueCharm value的最小值.
Sample input and output
| Sample Input | Sample Output |
|---|---|
4 43 4 12 3 21 2 42 4 3 | 1 |
Solve:
排序边权,枚举最小的边权,然后当1和n在同一个集合里的时候就更新答案,注意更新之前要判断1和n是不是在同一个集合里
Code:
1 #include <bits/stdc++.h> 2 using namespace std; 3 static const int MAXN = 1e3 + 10; 4 static const int OO = 0x3fffffff; 5 struct Node 6 { 7 int u , v , w; 8 }; 9 10 int father[MAXN];11 int high[MAXN];12 vector<Node> data;13 int n , m;14 int ans = OO;15 16 void Init()17 {18 for(int i = 0 ; i <= n ; ++i)19 {20 father[i] = i;21 high[i] = 0;22 }23 }24 25 int FindSet(int x)26 {27 if(x != father[x])28 father[x] = FindSet(father[x]);29 return father[x];30 }31 32 bool Same(int x , int y)33 {34 return (FindSet(x) == FindSet(y));35 }36 37 void Unite(int x , int y)38 {39 x = FindSet(x) , y = FindSet(y);40 if(x != y)41 {42 if(high[x] > high[y])43 father[y] = x;44 else45 {46 father[x] = y;47 if(high[x] == high[y])48 ++high[y];49 }50 }51 }52 53 int main()54 {55 scanf("%d%d" , &n , &m);56 for(int i = 1 ; i <= m ; ++i)57 {58 int a , b , c;59 scanf("%d%d%d" , &a , &b , &c);60 data.push_back({a , b , c});61 }62 63 sort(data.begin() , data.end() , [](Node a , Node b){return a.w < b.w;});64 int mx , mi;65 for(int i = 0 ; i < m ; ++i)66 {67 Init();68 mi = data[i].w;69 mx = mi;70 Unite(data[i].u , data[i].v);71 for(int j = i + 1 ; j < m ; ++j)72 {73 if(Same(1 , n))74 break;75 if(!Same(data[j].u , data[j].v))76 {77 Unite(data[j].u , data[j].v);78 mx = data[j].w;79 }80 }81 if(Same(1 , n))82 ans = min(ans , mx - mi);83 }84 85 printf("%d" , ans);86 }
2017 Training for Graph Theory
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。