题意就是给你一张无向连通图，试问对于图上所有点对（u，v）从u到v的所有路径中边权最大值的最小值的最大值。
定义f（u，v）表示从u到v所有路径中边权最大值的最小值，对所有点对取其最大。
实际上就是求图G的最小生成树的最大边权。
考虑kruskal算法流程，每次选取边权最小的且不产生圈的边加入mst。
至算法结束，图恰好连通，并且选取的边权都是最小的。
对于那些产生回路的边加入到mst中是没有意义的，因为之前保持图连通时选取的边权更小。
注意考虑重边。
http://poj.org/problem?id=2395
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <queue>
using namespace std;
typedef __int64 LL;
const int maxn = 2e3 + ;
const int maxm = 1e4 + ;
const int inf = 1e9 + 1e8;
struct Edge{
int from, to, next, c;
bool operator < (const Edge& rhs) const{
return c < rhs.c;
}
}edge[maxm << ];
struct Point{
int x, y, c;
bool operator < (const Point& rhs) const{
return x < rhs.x || (x == rhs.x && y < rhs.y) || (x == rhs.x && y == rhs.y && c < rhs.c);
}
};
int head[maxn], N;
Point a[maxm];
int n, m, k;
int ans;
bool vis[maxn]; void addEdge(int u, int v, int c){
edge[N].next = head[u];
edge[N].from = u;
edge[N].to = v;
edge[N].c = c;
head[u] = N++;
} int fa[maxn]; int find(int u){
if(fa[u] == - || fa[u] == u) return u;
return fa[u] = find(fa[u]);
}
int main(){
//freopen("in.txt", "r", stdin);
while(~scanf("%d%d", &n, &m)){
N = ;
memset(head, -, sizeof head);
for(int i = ; i < m; i++){
scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].c);
if(a[i].x > a[i].y) swap(a[i].x, a[i].y);
}
sort(a, a + m);
k = ;
for(int i = ; i < m; i++){
a[k++] = a[i];
while(i < m - && a[i].x == a[i + ].x && a[i].y == a[i + ].y) ++i;
}
for(int i = ; i < k; i++) addEdge(a[i].x, a[i].y, a[i].c);
sort(edge, edge + N);
int ans = -;
memset(fa, -, sizeof fa);
for(int i = ; i < N; i++){
int u = edge[i].from, v = edge[i].to;
int fu = find(u), fv = find(v);
if(fu != fv) fa[fv] = fu, ans = max(ans, edge[i].c);
}
printf("%d\n", ans);
}
return ;
}