*((W4, J4, W3, J3, W2, J2) – augmenting alternating path)A tree which has a root in some exposed vertex, and a property that every path starting in the root is alternating, is called an . Find(1)and replace existing labeling with the next one:(2)Now replace with Step 3. As an example we’ll use the previous one, but first let’s transform it to the maximum-weighted matching problem, using the second method from the two described above.*(Example on the picture above, with root in W4)That’s all for the theory, now let’s look at the algorithm: First let’s have a look on the scheme of the Hungarian algorithm: Step 0. (See Picture 1)Picture 1Here are the global variables that will be used in the code:#define N 55 //max number of vertices in one part#define INF 100000000 //just infinityint cost[N][N]; //cost matrixint n, max_match; //n workers and n jobsint lx[N], ly[N]; //labels of X and Y partsint xy[N]; //xy[x] - vertex that is matched with x,int yx[N]; //yx[y] - vertex that is matched with ybool S[N], T[N]; //sets S and T in algorithmint slack[N]; //as in the algorithm descriptionint slackx[N]; //slackx[y] such a vertex, that// l(slackx[y]) l(y) - w(slackx[y],y) = slack[y]int prev[N]; //array for memorizing alternating paths It’s easy to see that next initial labeling will be feasible: And as an initial matching we’ll use an empty one. The code for initializing is quite easy, but I’ll paste it for completeness: The next three steps will be implemented in one function, which will correspond to a single iteration of the algorithm.

For each vertex from left part (workers) find the minimal outgoing edge and subtract its weight from all weights connected with this vertex. Actually, this step is not necessary, but it decreases the number of main cycle iterations. Find the maximum matching using only 0-weight edges (for this purpose you can use max-flow algorithm, augmenting path algorithm, etc.). Step 2) Let and adjust the weights using the following rule: Step 3) Repeat Step 1 until solved.You open the Div I Medium and don’t know how to approach it, while a lot of people in your room submitted it in less than 10 minutes.Then, after the contest, you find out in the editorial that this problem can be simply reduced to a classical one.In other words, the sum of the labels of the vertices on both sides of a given edge are greater than or equal to the weight of that edge.be a spanning subgraph of G (in other words, it includes all vertices from G).But there is a nuance here; finding the maximum matching in step 1 on each iteration will cause the algorithm to become O(n5).In order to avoid this, on each step we can just modify the matching from the previous step, which only takes O(n2) operations.If G only those edges (x,y) which satisfy the following condition: , then it is an equality subgraph.In other words, it only includes those edges from the bipartite matching which allow the vertices to be perfectly feasible.Obviously, these edges will be the solution of the assignment problem.If we can’t find perfect matching on the current step, then the Hungarian algorithm changes weights of the available edges in such a way that the new 0-weight edges appear and these changes do not influence the optimal solution.

## Comments Assignment Problem Hungarian Method Maximization