题意
有多组样例输入。 对于每组样例，第一行为两个整数
n
(
2
≤
n
≤
100
)
,
m
(
0
≤
m
≤
n
∗
(
n
−
1
)
/
2
)
n(2≤n≤100),m(0≤m≤n*(n-1)/2)
n(2≤n≤100),m(0≤m≤n∗(n−1)/2)。 当
n
n
n和
m
m
m同时为
0
0
0代表结束输入。 接下来有
m
m
m行，每行三个整数
u
,
v
,
w
u, v, w
u,v,w。 问当选取一些边来使得
n
n
n个点联通时，最大边权-最小边权的差最小是多少，如果不能联通则输出
−
1
-1
−1。
思路
按边的权值从小到大排序，对每一条边先把其当做联通时权值最小的边，然后左端置为当前边的序号，右端设为边权值最大的边的序号。 再进行二分，利用并查集连边，如果边的下标取
l
l
l到
m
i
d
mid
mid可以使
n
n
n个点联通，就更新最小的答案。如果不存在联通的情况，
r
e
s
res
res最终会是
i
n
f
inf
inf，最后判断一下如果
r
e
s
res
res为
i
n
f
inf
inf则输出
−
1
-1
−1。
代码
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define ll long long
#define pi acos(-1.0)
using namespace std
;
struct node
{
int u
, v
, val
;
};
bool cmp(node a
, node b
){
return a
.val
<b
.val
;
}
int n
, m
, u
, v
, val
;
int f
[105], cnt
[105];
vector
<node
> vec
;
int find(int x
){
return (f
[x
]==x
? x
: f
[x
] = find(f
[x
]));
}
void join(int u
, int v
){
int fu
= find(u
), fv
= find(v
);
if (fu
!= fv
){
f
[fu
] = fv
;
cnt
[fv
] += cnt
[fu
];
}
}
bool solve(int s
, int e
){
for (int i
= 1; i
<= n
; i
++){
f
[i
] = i
;
cnt
[i
] = 1;
}
for (int i
= s
; i
<= e
; i
++){
int u
= vec
[i
].u
, v
= vec
[i
].v
;
join(u
, v
);
}
return cnt
[find(1)]==n
? true : false;
}
int main(){
while (scanf("%d%d", &n
, &m
) != EOF){
if (n
==0 && m
==0){
break;
}
int res
= inf
;
while (m
--){
scanf("%d%d%d", &u
, &v
, &val
);
vec
.push_back((node
){u
, v
, val
});
}
sort(vec
.begin(), vec
.end(), cmp
);
int sz
= vec
.size();
for (int i
= 0; i
< sz
; i
++){
int l
= i
, r
= sz
-1;
while (l
<= r
){
int mid
= (l
+r
)/2;
if (solve(i
, mid
)){
res
= min(res
, vec
[mid
].val
-vec
[i
].val
);
r
= mid
-1;
}
else{
l
= mid
+1;
}
}
}
printf("%d\n", res
==inf
? -1 : res
);
vec
.clear();
}
return 0;
}
