| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
Can anyone help me solve below problem?
Given an array with N numbers and given list of pair of integers u and v where each entry is two indices which cannot be together in chosen subset.Tell maximum possible size of such subset.
Don't worry about constraints tell your best solution.
Maximum independent set. Polynomial (even linear) in some graphs.
Thanks AlexandruValeanu for the reference,Original problem which I simplified to above problem was given array with N numbers find subset such that product of any two numbers in subset is not cube. 1<=N<=100 and number in 1<=array<=1000000 and 1 is cube. Any thoughts on how to solve it.
I think it's a bipartite graph, so Max independent set problem can be solved by creating the flow network and getting the max flow, so the answer to the problem is:
Ans = TotalNodesNumber - MaxFlow
Can subset contain a cube? If it is so final graph can contain one clique of cubes in addition to bipartite part.