Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
Statistical Charts
Submit Problem
Online Status
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Minimum Weighted Perfect Fractional b-Matching
Time Limit: 1000MSMemory Limit: 131072K
Total Submissions: 110Accepted: 47


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,

\sum_{e\in E(v)}x(e)=b(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

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

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, yn, 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.

Sample Input

4 3
3 1 6 4
3 1 10 4
2 3 2 2
2 1 6 6

Sample Output



[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