題意：求一條路徑，使得這條邊連接1到n，求邊權值的最大值與最小值的差
題解：最小生成樹，對邊權排序，可以枚舉邊的最大和最小的值，判斷能否使得1和n連通
#include <bits/stdc++.h> #define ll long long #define maxn 1010 using namespace std; struct edge{ll from,to,weight; }; int cmp(edge a,edge b){return a.weight<b.weight; } vector<edge>edges; int fa[maxn]; int find(int x){return x==fa[x]?x:(fa[x] = find(fa[x])); } void init(int n){for(int i=1;i<=n;i++) fa[i] = i; } int main(){ll n,m,i,j,a,b,c, ma = -1e17,mi = 1e17, ans = 1e18;cin>>n>>m;for(i=0;i<m;i++){cin>>a>>b>>c;edges.push_back((edge){a,b,c});}sort(edges.begin(), edges.end(), cmp);for(i=0;i<m;i++){init(n);mi = 1e17;ma = -1e18;for(j=i;j<m;j++){edge e = edges[j];mi = min(e.weight, mi);ma = max(e.weight, ma);int fau = find(e.from);int fav = find(e.to);if(fau != fav) fa[fau] = fav;if(find(n) == find(1)) break;}if(j<m) ans = min(ans, ma-mi);}cout<<ans<<endl;return 0; }
?
