如有错误,请留言提醒,不要坑到小朋友
Description
华英雄最喜欢玩暴力摩托,一个通宵之后,总算过了全关!正当他为自己的成绩洋洋得意的时候却发现居然还有一个特别的附加关!华英雄虽然累得眼睛都睁不开了,但是他还是决定再试一试!
这一关与以前的关不同,包含有N个站,之间连了M条双向的通路!但每条路都规定了一个Speed值,在这条路上必须以这个速度前进!所以在前进的时候要频繁的调整速度,这对鱼类来说是很痛苦的,所以华英雄决定尽量使调整的幅度小一些,也就是使走过的路的速度最大值与最小值之差最小!
可最近华英雄由于沉溺在暴力摩托中,已经荒废了编程技术,所以只有请你来帮忙了!^_^
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
这哪里可以用到并查集呢
那就是判断两个点的联通性
首先我们把所有的边从小到大排序
然后我们一个一个添边直到起点,终点联通
#include<iostream> int fa[201],x,y,n,m; struct dd { int x,y,len; }line[1001]; int cmp(const void *a,const void *b) { return (*(dd *)a).len>(*(dd *)b).len?1:-1; } int find(int f) { if(fa[f]==f)return f; return fa[f]=find(fa[f]); } void work() { int q,p,i,j,k; int ans=999999999; for(i=1;i<=m;i++) { for(j=1;j<=n;j++) fa[j]=j; for(j=i;j<=m;j++) { q=find(line[j].x); p=find(line[j].y); if(q!=p)fa[q]=p; if(find(x)==find(y))break; } if(fa[x]==fa[y]) ans=ans<line[j].len-line[i].len?ans:line[j].len-line[i].len; } printf("%d\n",ans); } int main() { // freopen("data.in","r",stdin); // freopen("data.out","w",stdout); int i,j,k; scanf("%d%d",&n,&m); for(i=1;i<=m;i++) scanf("%d%d%d",&line[i].x,&line[i].y,&line[i].len); qsort(line,m+1,sizeof(line[1]),cmp); scanf("%d",&k); for(i=1;i<=k;i++) { scanf("%d%d",&x,&y); work(); } }