Блог пользователя KzNuRs

Автор KzNuRs, история, 7 лет назад, По-английски

How to solve?

  • Проголосовать: нравится
  • -14
  • Проголосовать: не нравится

»
7 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I don't think this is a min-flow max cut problem...

  • »
    »
    7 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +34 Проголосовать: не нравится

    Yes, because min flow can be solved in O(1).

  • »
    »
    7 лет назад, скрыть # ^ |
    Rev. 2  
    Проголосовать: нравится +9 Проголосовать: не нравится

    You can frame it as one, I believe. I think you can reduce it to the following problem:

    You are given $$$n$$$ boxes of varying dimensions $$$l_i \times w_i \times h_i$$$, and we say that box $$$i$$$ can be nested in box $$$j$$$ iff $$$l_i \lt l_j$$$, $$$w_i \lt w_j$$$, and $$$h_i \lt h_j$$$. You can stack nesting, i.e. if box $$$i$$$ can be nested in box $$$j$$$ and box $$$j$$$ in box $$$k$$$, then, you can nest $$$i$$$ into $$$j$$$ and $$$j$$$ into $$$k$$$, meaning neither box $$$i$$$ nor box $$$j$$$ is visible anymore. Given our $$$n$$$ boxes, we want to nest the boxes in such a way to reduce the total number of visible boxes.

    The above problem appeared on my algorithms homework, and the solution used max flow.

    I think the solution is cool but I don't actually want to write it, because I'm still not convinced that this problem isn't OP's homework problem (he posted it before with a download link to the image, and it was called "Assignment7.pdf").