How can I get anti-integer elements in SPOJ-DIVREL?

Question

Problem: http://www.spoj.com/problems/DIVREL

In the question, we just need to find the maximum number of elements that are not multiple (divisible in form b) from the set of given elements. If we just make an edge from an element to its plural and build a graph, it will be a DAG.

Now the question is only changing to finding the minimum number of chains that contain all vertices equal to the powers of antichin using the Dilworth theorem , since it is a partially ordered set.

Minimum chains can be found using bipartisan matching (How: Minimum path coverage), but now I can not find the anti-integer elements themselves?

Answer 1

To calculate anticein, you can:

• Calculate the maximum two-way correspondence (for example, using the maximum flow algorithm ) on a new bipartite graph D that has an edge from LHS a to RHS b if and only if a divides b.
• Use matching to calculate the minimum coverage of vertices (for example, with the algorithm described in the proof of Koenig's theorem
• Antihein is defined by all vertices not in the vertex coverage

There cannot be an edge between two such elements, since otherwise we would find an edge that is not covered by a vertex, resulting in a contradiction.

Mine top vertex search algorithm (from the link above):

• Let S0 consist of all vertices that do not coincide with M.
• For an integer j ≥ 0, let S (2j + 1) be the set of all vertices v for which v is adjacent through some edge in E \ M to a vertex from S (2j) and v is not included in Any predefined set Sk, where k <2j + 1. If there is no such vertex, but there remain vertices not included in any previously defined set Sk, arbitrarily choose one of them and let S (2j + 1) consist of a single vertex.
• For an integer j ≥ 1, let S (2j) be the set of all vertices u such that u is adjacent through some edge in M ​​to a vertex from S (2j-1). Note that for every v from S (2j-1) there exists a vertex u to which it maps since otherwise v would be in S0. Therefore, M establishes a one-to-one correspondence between the vertices S (2j-1) and the vertices S (2j).

The union of odd indexed subsets is a vertex covering.