Python 代码
import sys
sys.setrecursionlimit(1000000)
N, M = map(int, input().split())
h, e, ne, wei = [-1] * (N+1), [0] * (2*M+1), [0] * (2*M+1), [0] * (2*M+1)
idx = 0
color = [0] * (N+1)
def add(a, b, w):
global idx
e[idx], wei[idx] = b, w
h[a], ne[idx] = idx, h[a]
idx += 1
def dfs(x, c, limit):
color[x] = c
i = h[x]
while i != -1:
j, w = e[i], wei[i]
if w > limit:
if color[j]:
if color[j] == c:
return False
elif not dfs(j, 3-c, limit):
return False
i = ne[i]
return True
def check(limit):
for i in range(1, N+1):
color[i] = 0
for i in range(1, N+1):
if color[i] == 0:
if not dfs(i, 1, limit):
return False
return True
max_w = 0
for i in range(M):
a, b, w = map(int, input().split())
add(a, b, w)
add(b, a, w)
max_w = max(max_w, w)
l, r = 0, max_w
while l < r:
mid = l + r >> 1
if check(mid): r = mid # 如果满足则说明当前limit需要减小
else: l = mid + 1
print(l)