|Online Judge||Problem Set||Authors||Online Contests||User|
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,
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
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(vi) (1 ≤ b(vi) ≤ 200), the balance of vertex i.
Output the weight of the found matching.
4 3 3 1 6 4 3 1 10 4 2 3 2 2 2 1 6 6 2 2 4
[Submit] [Go Back] [Status] [Discuss]
Home Page Go Back To top
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator