# 查找具有約束的循環

## 最佳答案

If you allow $k/2$ without integer division, then you can reduce your problem to computing the maximum mean weight cycle. Replace every undirected edge by two directed egdes. Every edge leaving a node $A_i$ gets value $B(i)$. Compute a cycle of maximum mean weight (i.e., with maximum average edge weight). You condition is violated if and only if the maxium mean weight is $> 1/2$.