题意：给n个点，m条边，和每条边的权值，求从s点到e点 路径 权差 的最小值，即边权值最大的减去最小的。
原始最小生成树可以做的：求连接图所有节点 的最小权值和。
kruskal算法使用的结构：并查集，对边权排序。
kruskal算法的实现过程：
1：输入边，权
2：对权 从小到大 排序
3：按权值 从小到大考虑 ，
是否可以连接这条边（成环则不可连，不成环可连）
判断成环与否和连接 环的操作使用并查集实现 ：
若该边的两个节点都在同一个并查集枝上，则成环
连接 就是用并查集连接
就本题来说：
目的：求从s点到e点 路径 权差 的最小值
kruskal算法的操作：按权值从小到大连边，那么s和e连接完毕时的边权时最大的权，起始的边权时最小的，起始边权从所有边权最小开始
在可以连通s和e的前提下， 第一个连接的边权 应尽量 大 ， 最后连接的边权尽量 小
判断s和e连通的标志： 它们的老大是同一人
关键代码：
void ckruskal() { fin=1e9; for(int i=0;i<m;i++) { for(int j=0;j<205;j++) pre[j]=j; k=m-1;flag=0; for(int j=i;j<m;j++){ int r=f(e[j].u) ,t=f(e[j].v); if(r!=t) pre[r]=t; if(f(s)==f(en)){k=j; flag=1; break;} } if(!flag) break; fin=min(e[k].w-e[i].w,fin); } }
完整代码：
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 struct edge 5 { 6 int u,v,w; 7 }e[1005]; 8 int n,m,q,k,s,en,fin,pre[205]; 9 bool flag; 10 bool cmp(edge a,edge b){return a.w<b.w;} 11 12 void input() 13 { 14 for(int i=0;i<m;i++) 15 scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w); 16 sort(e,e+m,cmp); 17 } 18 19 int f(int x){return x==pre[x]?x:pre[x]=f(pre[x]);} 20 21 void ckruskal() 22 { 23 fin=1e9; 24 25 for(int i=0;i<m;i++) 26 { 27 for(int j=0;j<205;j++) pre[j]=j; 28 k=m-1;flag=0; 29 for(int j=i;j<m;j++){ 30 31 int r=f(e[j].u) ,t=f(e[j].v); 32 if(r!=t) pre[r]=t; 33 if(f(s)==f(en)){k=j; flag=1; break;} 34 } 35 if(!flag) break; 36 fin=min(e[k].w-e[i].w,fin); 37 } 38 } 39 int main() 40 { 41 while(scanf("%d%d",&n,&m)!=EOF) 42 { 43 input(); 44 cin>>q; 45 while(q--) 46 { 47 scanf("%d%d",&s,&en); 48 ckruskal(); 49 if(fin!=1e9)printf("%d\n",fin); 50 else printf("-1\n"); 51 } 52 53 } 54 return 0; 55 } View Code
转载于:https://www.cnblogs.com/star-and-me/p/6715436.html
相关资源：各显卡算力对照表！