暴力摩托

news/2025/4/2 6:17:37/

Description

N个站，之间连了M条双向的通路！但每条路都规定了一个速度的限制值，在这条路上必须以这个速度前进！所以在
前进的时候要调整速度，现决定尽量使调整的幅度小一些，也就是使走过的路的速度最大值与最小值之差最小！

Input

第一行有2个正整数N , M , 分别表示站点数，路径数.
接下来M行，每行有3个正整数 X, Y, V表示X， Y之间有一条路，其Speed值是V。
再接下来是数K，表示任务数，
下面K行，每行有一对正整数P，Q ，表示一个任务从P到Q.
(1<=n<=200, 1<=m<=1000, 1<=K<=10)

Output

对于每一个任务输出一行，仅一个数，即最大速度与最小速度之差。

Sample Input

4 4
1 2 2
2 3 4
1 4 1
3 4 2
2
1 3
1 2

Sample Output

1
0

本题大意：
有n个节点和m条边（现告诉你每条边的起点和终点），并且在每一条边上有一个权值。现有k条指令，每条指令告诉你x（起点）和y（终点），现要求每条指令的从x点到y点所经过的最大权值和最小权值的差越小越好，并输出结果。

题解：
相信有很多人和我一样，在看到这道题的时候最先想到的就是树或是dfs，但再看看数据范围，能不能过自己心里也没底，最后看看标签 “并查集” ，顿时摸不着头脑，接着就放弃了。
其实，这题也没有这么难，我们可以用并查集来优化。
由于要使两者差最小，则必须使最大值尽可能的小，使最小值尽可能的大。
步骤：
1、我们先按每一条边的值从小到大排序（至于为什么，后面会讲到）
2、接着，我们可以枚举最最小权值的边，在以这条边为起点，去搜索能使x和y两点相连的路线（这里需要运用并查集，若两者的根相同，则可以相连），找到一条能使x和y相连的最大权值的边，就跳出循环（由于之前已经排好序，所以在它后面的，肯定会比当前值大），继续枚举。
3、若能够相连，则以当前值的差与小差去作比较，取较小值。
4、一次打印一个即可。

代码实现如下：

#include<bits/stdc++.h>
using namespace std;
int f[201],x,y,n,m;
struct dd {int x,y,z;//x、y为这条边的两个结点，z为权值
} v[1001];
bool cmp(dd a,dd b) {return a.z<b.z;
}
int find(int i) {if(f[i]==i) return i;return f[i]=find(f[i]);//并查集，扁平化使时间缩短
}
void work() {int i,j,ans=INT_MAX;for(i=1; i<=m; i++) {//枚举最小值for(j=1; j<=n; j++)f[j]=j;//初始化for(j=i; j<=m; j++) {//枚举最大值，保证最大值比最小值大if(find(v[j].x)!=find(v[j].y))//若当前边还未相连，则把两点相连f[find(v[j].x)]=find(v[j].y);if(find(x)==find(y))//若找到路线，则退出循环break;}if(f[x]==f[y])//若以当前值为最小值，且x与y能够相连，则去作比较ans=min(ans,v[j].z-v[i].z);//最大值减去最小值}printf("%d\n",ans);
}
int main() {int i,j,k;scanf("%d%d",&n,&m);for(i=1; i<=m; i++)scanf("%d%d%d",&v[i].x,&v[i].y,&v[i].z);sort(v+1,v+m+1,cmp);//排序scanf("%d",&k);for(i=1; i<=k; i++) {scanf("%d%d",&x,&y);work();}
}