3611：Minimum Weighted Perfect Fractional b-Matching

In graph theory, a matching M of a graph G = (V,E) is defined as a pairwise disjoint subset of E. Put alternatively, a matching M of G is a subset of E such that each vertex covered by M is incident to exactly one edge in M. A perfect matching M of G is a matching that covers all vertices of G.

Extending the definition of a matching, the concept of b-matching is based on a graph G where each vertex v is associated with a non-negative integral balance b(v) and each edge e with a non-negative integral capacity u(e). A b-matching M of G is defined as an assignment of a non-negative integral bidirected flow x(e) ≤ u(e) to each edge e. A perfect b-matching is a b-matching where for each vertex v,

__poj_jax_start__\sum_{e\in E(v)}x(e)=b(v)__poj_jax_end__,

in which E(v) denotes the set of all edges incident to v. Intuitively speaking, a perfect b-matching is a generalized perfect matching that allows each vertex to be incident to multiple edges and each edge to be used multiple times. A perfect fractional b-matching is a relaxation of a perfect b-matching. A perfect b-matching demands the integrality of the flows, whereas a perfect fractional b-matching permits that they take fractional values. Associating a weight c(e) with each edge e of G, the weight of a perfect fractional b-matching is defined as

__poj_jax_start__\sum_{e\in E}c(e)x(e)__poj_jax_end__.

A minimum weighted perfect fractional b-matching is defined as the perfect fractional b-matching with the minimum weight.

Given a capacitated, weighted graph with a balance constraint on each vertex, find a minimum weighted perfect fractional b-matching.　

The first line contains two integers m and n, (1 ≤ m ≤ 1000, 1 ≤ n ≤ 100), the numbers of edges and vertices of the graph. The vertices are numbered 1 through n.

The next m lines each contain four integers x, y, u(e) and c(e) (1 ≤ x, y ≤ n, 1 ≤ u(e) ≤ 200, 1 ≤ c(e) ≤ 200) describing an edge e, where x and y are the endpoints of e, and u(e) and c(e) are the capacity and the weight of e, respectively.

The last n lines each contain an integer b(v_i) (1 ≤ b(v_i) ≤ 200), the balance of vertex i.