Balanced weighting of edges in cactus graph
So this question has been bothering me: why a cactus, if there's already a linear-time algorithm for a more general class?

The primal problem is known as the fractional matching problem, and, unsurprisingly, it has been studied as well. Balinski (whose result was made known to me via Schrijver's book Combinatorial Optimization) characterized the extreme points of the fractional matching polytope as consisting of an integer matching plus half of a collection of odd cycles. Given the relatively low input limits, I suspect that the intended solution of the problem poser was to modify Edmonds's blossom algorithm in a way that, for now, I will leave for you to discover. The structure of the cycles in a cactus makes this algorithm simple enough to be appropriate for a contest.



As sxu points out, this problem is amenable to linear programming. If you need just the objective value, the dual LP has the same objective value and is the fractional vertex cover problem. The nice thing about vertex cover is that it has a half-integral optimum; in linear time, you can use depth-first search to compute a tree decomposition of the cactus of width O(1) and solve the dual LP with a dynamic program that tries variable values in {0, 1/2, 1}.

If you actually need a solution for the primal, then complementary slackness might help, but I can't help but suspect that the restriction to cacti is supposed to allow a more elementary solution.