10779 WA

[Ra1nWarden]

Failed for the following test case

1 6 20 15 20 2 1 16 15 9 20 16 7 14 1 15 6 7 20 42 16 20 7 6 4 10 5 11 6 3 4 19 19 17 18 19 10 10 6 16 19 5 11 17 19 4 11 16 10 10 14 6 1 20 3 5 1 7 15 6 2 10 11 20 6 13 18 16 3 4 11 13 20 14 1 10 23 11 18 6 1 11 3 13 3 17 9 3 4 15 1 17 4 16 16 10 9 6 17 11 26 19 15 20 12 3 10 8 5 19 6 5 9 20 18 3 17 18 18 20 13 18 16 16 13 3 17

output is supposed to be 13 but my code returns 12

Algorithm used: Maximum flow: add a super source connecting each sticker node with capacity equal to the number of that sticker Bob has. Add a super sink connecting from all sticker nodes with capacity 1.

[Ra1nWarden]

The problem is about the absence of back edge: When a directed edge is added, a back edge of capacity 0 should be added. See the following change: https://github.com/Ra1nWarden/UVa-Online-Judge/commit/f40899c66d1a97be2fc63f1621ccb5dea680c965#diff-a489206a893793ba47fab4fdc4772078R63

[Ra1nWarden]

The back edge should also be added to the adjList i.e. destination's adjacency list should have the source node.

[Ra1nWarden]

The difference between a directed and undirected graph is in the adjacency matrix: directed: back edges have weight 0 undirected: back edges have the same weight as forward edges