I have an undirected bipartite graph with N nodes in set A and M nodes in set B, where N <= 50000 and M <= 1000. There can be N * M edges. Each node from set A can mark either zero or two nodes from set B if there is an edge between the node from set A and each of the two nodes from set B. Each node from set B can be marked only once by only one node from set A. I need to find the maximum number of nodes that can be marked from set B.
I'm stuck with this problem. Any kind of help is very much appreciated.
This is a wrong solution to the problem This is basically maximum matching with the condition that each node in a can connect to two nodes in b. Since the number edges is huge. we can reduce it by connecting all nodes in a to a node and all nodes in b to that node. Then run dinics algorithm complexity O((n + m)sqrr(n + m)).
Can you give me hints on how to add edges (capacity?) in the new graph for applying Dinic's algorithm? Also, total number of edges isn't always N * M, only when number of edges is maximum. It seems that if we connect every node in A to a common node and every node in B to that same node then it is helping only when number of edges is N * M. And every node in set A must mark exactly two or zero nodes from set B (marking only one isn't allowed). Are you considering that?
Can you please please share the link. Also, how are the edges given?
I am trying to solve "Alien Rhyme" from GCJ Round 1A 2019 using this approach. I am assuming the set of all suffixes as nodes of set A and the indexes of the strings as nodes of set B. I know good analysis and editorials exist for this problem but I was wondering if I could solve it like this anyway. Here is the link to the problem.
while redusing the problem to a graph problem you lost some important informations about the problem... (hint: if $$$s_i .. s_j$$$ is a common suffix then $$$s_{i+1}..s_j$$$ is also a common suffix)
I don't see why that will be a problem. Can you give me an example where this approach will not work?
the reduction is correct (a result for the graph problem is a valid solution for the original problem). But the graph problem is harder to solve than the original problem...
The problem you are reducing to is the same as "Bimatching" from the last neerc, where the intended solution is in $$$O(n^{5/2})$$$
Thank you very much :)