Hi, in this problem from HackerRank we abstract the problem to a directed graph with capacity and cost on the edges, source and sink and we need to get the minimum cost despite the flow (as long as we don't exceed the capacities).

To achieve that, we just need to change the Max Flow Min Cost algorithm breaking it when the best augmenting path we found has total cost greater than zero. Link to editorial: here (he changed the problem to Maximum Cost so he breaks it when the best augmenting path has cost smaller than zero).

My doubt is: Does this algorithm to get Minimum Cost with "Any Flow" work specifically for this problem's class of graph or does it work for every other cost-flow graph?

Hi I'm having trouble with the 2-CNF (Conjuctive Normal Form) problem, not just 2-SAT but the more general case of Conjuctive Normal Forms, ie: a => b (a implies b), c => ¬d (c implies not d). I've got some doubts, if you can help me with any of them it would help me a lot.

1 — What is the answer for the case (a => b) and (b => ¬a) and (¬a => c) and (c => d) and (d => ¬c)? I think its not satisfiable but if you solve like 2-SAT by just checking for all x if x and ¬x are in the same SCC then getting the variable with higher toposort between (x and ¬x) as the answer you may come to a diferrent result.

2 — There is an algorithm to find if some 2-CNF is solvable? And if its solvable how can we get some solution?

3 — If x or ¬x has not in edge nor out edge in the graph of implications, its correct to just set it as the answer? If you just get the toposort values like in 2-SAT algorithms, x or ¬x can be set as answer depending of how you do the toposort, but in some cases I think it doenst work.

Ex: (a => b) and (b => ¬a) and (¬a => c). If we dont treat it the toposort of ¬c can be grater than toposort of c and ¬c may be setted as the answer, but it is mandatory that ¬a is in the answer so c is in the answer.

4 — There is a way to calculate the total number of ways of chose the values of variables to get a satisfiable solution?