1

Тема: Максимальное число вложенных параллелепипедов

Привет,

Условие задачи простое: найти максимальное количество вложенных параллелепипедов.
Параллелепипед может входить в другой только тогда, когда размеры его сторон строго меньше.

1?N?100
1?x,y,z?1000000


Пример входных данных:
4
1 1 1
2 2 2
3 4 5
4 3 2

Пример выходных данных:
3

У меня есть решение и оно не проходит все тесты.
Я не знаю где ошибка, на каком тесте заваливается по ВА.
Помогите пожалуйста, определить случай, когда этот код выдает ВА:

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

#define X 0
#define Y 1
#define Z 2

struct CSuitCase
{
    int m_size[3];
    void Normalize()
    {
        sort(m_size, m_size+3);
    }
    bool operator < (const CSuitCase & suit2) const
    {
        bool bRetVal = false;

        if(m_size[X] < suit2.m_size[X] && 
            m_size[Y] < suit2.m_size[Y] && 
            m_size[Z] < suit2.m_size[Z])
        {
            bRetVal = true;
        }

        return bRetVal;
    }
};

bool matr[101][101];
int maxs[101];
void dfs(int v, vector<int> vect)
{

    vect.push_back(v);
    
    for(size_t i = 0; i < 101; ++i)
    {
        if(matr[i][v])
        {
            if(maxs[i] == 0)
            {
                dfs(i, vect);
            }
        }
    }

    for(size_t i = 0; i < vect.size(); ++i)
    {
        int m = vect.size() - i;
        if(m > maxs[vect[i]] )
        {
            maxs[vect[i]] = m;
        }
    }

    vect.pop_back();
}

int main()
{
    vector<CSuitCase> suitcases;

    memset(maxs, 0, sizeof(int)*101);

    int nSuitCaseNumber;
    cin >> nSuitCaseNumber;

    for(size_t i = 0; i < nSuitCaseNumber; ++i)
    {
        CSuitCase suitCase;
        scanf("%d %d %d", &suitCase.m_size[X], &suitCase.m_size[Y], &suitCase.m_size[Z]);
        suitCase.Normalize();
        suitcases.push_back(suitCase);
    }
    
    sort(suitcases.begin(), suitcases.end());
/*
    for(size_t i = 0; i < suitcases.size(); ++i)
    {
        printf("%d %d %d\n", suitcases[i].m_size[X], suitcases[i].m_size[Y], suitcases[i].m_size[Z]);
    }
*/
    //
    // Initialization
    for(size_t i = 0; i < 101; ++i)
    {
        for(size_t j = 0; j < 101; ++j)
        {
            matr[i][j] = false;
        }
    }
    //
    // Creating of matr
    for(size_t chosen = 0; chosen < suitcases.size(); ++chosen)
    {
        for(size_t i = chosen + 1; i < suitcases.size(); ++i)
        {
            if(suitcases[chosen] < suitcases[i])
            {
                matr[i][chosen] = true;
            }
        }
    }


    //
    // Search for longest path
    for(size_t i = 0; i < suitcases.size(); ++i)
    {
        vector<int> vect;
        dfs(i, vect);
    }
    
    int nMax = 0;
    for(size_t i = 0; i < 101; ++i)
    {
        if(maxs[i] > nMax)
        {
            nMax = maxs[i];
        }
    }

    cout << nMax;


    return 0;
}

Тому, кто найдет ответ, буду очень благодарен !

2

Re: Максимальное число вложенных параллелепипедов

Я на код почти не смотрел. Но, насколько знаю, эта задача решается максимальным паросочетанием.

3

Re: Максимальное число вложенных параллелепипедов

aza_inf пишет:

Я на код почти не смотрел. Но, насколько знаю, эта задача решается максимальным паросочетанием.

Эта задача решается поиском в глубину. Ну точнее, динамикой с запоминанием, которая оформляется в виде одного поиска в глубину.

4

Re: Максимальное число вложенных параллелепипедов

KADR пишет:
aza_inf пишет:

Я на код почти не смотрел. Но, насколько знаю, эта задача решается максимальным паросочетанием.

Эта задача решается поиском в глубину. Ну точнее, динамикой с запоминанием, которая оформляется в виде одного поиска в глубину.

Я так и сделал