思路：
留意到題目里面有一句話“All farms are connected one way or another to Farm 1.”。
這貌似說明圖一開始就是連通的。
二分答案，判斷依據(jù)是：
如果將大于某個(gè)長度的邊都去掉以后，圖就不連通了。
那這個(gè)長度相對(duì)答案來說，一定是大了。
#include <stdio.h>
#define MAX_M 10032
#define MAX_N 2048
struct edge_node 
{
int idx, len;
struct edge_node *next;
};
struct edge_node edges[MAX_M*2], *map[MAX_N];
int N, M, vis[MAX_N], tm, stk[MAX_N], *sp;
inline int can(int limit)
{
int cnt;
struct edge_node *e;
tm++;
sp = stk;
*sp++ = 1;
vis[1] = tm;
cnt = 0;
while (sp > stk) {
sp--;
cnt++;
for (e = map[*sp]; e; e = e->next) {
if (vis[e->idx] == tm || e->len > limit)
continue;
vis[e->idx] = tm;
*sp++ = e->idx;
}
}
return cnt == N;
}
inline void insert(struct edge_node *e, int a, int b, int len)
{
e->idx = b;
e->len = len;
e->next = map[a];
map[a] = e;
}
int main()
{
int l, r, m, i, a, b, len;
scanf("%d%d", &N, &M);
l = 0x7fffffff;
r = 0;
for (i = 0; i < M*2; i += 2) {
scanf("%d%d%d", &a, &b, &len);
insert(&edges[i], a, b, len);
insert(&edges[i + 1], b, a, len);
if (len < l)
l = len;
if (len > r)
r = len;
}
while (l <= r) {
m = (l + r) / 2;
if (!can(m))
l = m + 1;
else
r = m - 1;
}
printf("%d\n", r + 1);
return 0;
}