HDU 1598 find the most comfortable road
枚举最小边权，找MST，在这个过程中，当起点和终点连在一起之后，就是一个差值枚举完所有的边，找到差值最小这个过程中总是可以找到使得两点间的边权最大差值最小的路径，没有反例就是证明
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <stack>
#include <list>
#include <map>
#define INF 0x3f3f3f3f
#define lowbit(x) x & (- x)
using namespace std
;
typedef long long ll
;
typedef unsigned long long ull
;
const int maxN
= 200 + 5;
const int maxM
= 1000 + 5;
int n
, m
;
struct node
{
int u
, v
, w
;
node(int a
= 0, int b
= 0, int c
= 0) : u(a
), v(b
), w(c
) {}
friend bool operator < (node n1
, node n2
) { return n1
.w
< n2
.w
; }
}info
[maxM
];
int root
[maxN
], child
[maxN
], high
[maxN
];
void init()
{
for(int i
= 0; i
<= n
; i
++ )
{
root
[i
] = i
;
child
[i
] = 1;
high
[i
] = 0;
}
}
int Find(int x
) { return root
[x
] == x
? x
: root
[x
] = Find(root
[x
]); }
int Same(int x
, int y
) { return Find(x
) == Find(y
); }
void Merge(int x
, int y
)
{
x
= Find(x
); y
= Find(y
);
if(child
[x
] < child
[y
] || high
[x
] < high
[y
])
{
root
[x
] = y
;
child
[y
] += child
[x
];
}
else
{
root
[y
] = x
;
child
[x
] += child
[y
];
if(high
[x
] == high
[y
]) high
[x
] ++;
}
}
int Kruskal(int st
, int ed
)
{
int min_
, max_
, dif
= INF
;
for(int k
= 0; k
< m
; k
++ )
{
init();
min_
= info
[k
].w
;
for(int i
= k
; i
< m
; i
++ )
{
if(!Same(info
[i
].u
, info
[i
].v
))
{
Merge(info
[i
].u
, info
[i
].v
);
if(Same(st
, ed
))
{
max_
= info
[i
].w
;
dif
= min(dif
, max_
- min_
);
break;
}
}
}
}
if(dif
== INF
)
return -1;
return dif
;
}
int main()
{
while(~scanf("%d%d", &n
, &m
))
{
for(int i
= 0; i
< m
; i
++ )
scanf("%d%d%d", &info
[i
].u
, &info
[i
].v
, &info
[i
].w
);
sort(info
, info
+ m
);
int q
; scanf("%d", &q
);
while( q
-- )
{
int s
, e
;
scanf("%d%d", &s
, &e
);
printf("%d\n", Kruskal(s
, e
));
}
}
return 0;
}
