Загрузка...

Граф сумма ребер

Тема в разделе C/C++ создана пользователем oriole 20 дек 2020. 203 просмотра

  1. oriole
    oriole Автор темы 20 дек 2020 был(а) давно
    с++
    Найти сумму всех дуг, что выходят с определенной вершины.

    [IMG]

    допустим если я указываю вершину 2 результат должен быть 26
    выходят два ребра каждое с весом 13
    есть какие-то идеи ? )
    или кто сделает заплачу 200р :cool_bun:
    уже сделал
     
    20 дек 2020 Изменено
  2. dragoniil
    dragoniil 20 дек 2020 НА ПИВО КИНЬТЕ ПЖ 555 6 авг 2018
    #include <iostream>
    #include <iomanip>
    #include <vector>
    using namespace std;

    #define cr(a, b, x, y) case a: return CellCoord{b, x, y}
    #define SIDENUM 3 //количество сторон куба которые хранятся
    #define MAX_L 51 //максимальное значение L

    #define BASE 1000000000 //10^9, основание системы счисления для длинной арифметики
    #define DNUM 9 //количество цифр 10-ичной системы счисления в 1 "цифре" длинной арифметики

    struct LongNum {
    //реализация длинной арифметики на векторах со сложением и выводом
    vector<int> v;
    LongNum() {} //стандартный конструктор
    LongNum(int s) { //конструктор из int
    v.push_back(s);
    }
    void print() { //вывод числа
    cout <<(v.empty() ? 0 : v.back());
    for (int i = (int)v.size() - 2; i>=0; i--)
    cout <<setfill('0') <<setw(DNUM) <<v;
    }
    void add(LongNum term) { //прибавление длинного числа
    auto b = term.v;
    int carry = 0;
    for (size_t i = 0; i < max(v.size(), b.size()) || carry; i++) {
    if (i == v.size())
    v.push_back(0);
    v += carry + (i < b.size() ? b : 0);
    carry = v >= BASE;
    if (carry) v -= BASE;
    }
    }
    };

    struct CellCoord {
    //хранит данные о положении клетки
    short side;
    short x, y;
    };

    struct CellNeighbors {
    //хранит данные о положении всех(4) соседей определённой клетки
    CellCoord n[4];
    };

    CellCoord FixNeighbor(short l, short side, short x, short y) {
    //исправляет данные о положении клетки, если она выходит за края грани
    if(x == -1) { //если сосед находится левее грани
    switch(side) {
    //если координаты выходят за левую границу 0-ой грани - меняет грань на 1-ую,
    //обнуляя y, а в x записывает старый y
    cr(0, 1, y, 0); //и так далее
    cr(1, 1, l-1, y);
    cr(2, 1, l-y-1, l-1);
    }
    } else if(x == l) {//правее
    switch(side) {
    cr(0, 1, l-y-1, 0);
    cr(1, 1, 0, y);
    cr(2, 1, y, l-1);
    }
    } else if(y == -1) {//выше
    switch(side) {
    cr(0, 1, l-x-1, 0);
    cr(1, 0, x, l-1);
    cr(2, 1, x, l-1);
    }
    } else if(y == l) {//ниже
    switch(side) {
    cr(0, 1, x, 0);
    cr(1, 2, x, 0);
    cr(2, 1, l-x-1, l-1);
    }
    } else {
    // если координаты не вышли за границы грани просто возвращаем неизменёные координаты
    return CellCoord{side, x, y};
    }
    }

    CellNeighbors GetNeighbors(short l, short side, short x, short y) {
    //возвращает исправленные координаты всех(4) соседних клеток
    return CellNeighbors{{
    FixNeighbor(l, side, x-1, y),
    FixNeighbor(l, side, x+1, y),
    FixNeighbor(l, side, x, y-1),
    FixNeighbor(l, side, x, y+1)
    }};
    }

    int main() {
    short l, m;
    bool flag = false;
    cin >>l >>m;
    LongNum cubes[2][SIDENUM][MAX_L][MAX_L];

    cubes[0][0][l/2][l/2] = LongNum(1);
    //за 0 ходов можно дойти 1 путём в изначальную точку

    CellNeighbors nbs[SIDENUM][MAX_L][MAX_L];
    //массив координат соседей

    for(short side=0; side<SIDENUM; side++) {
    for(short xi=0; xi<l; xi++) {
    for(short yi=0; yi<l; yi++) { //перебор координат всех клеток
    nbs[side][xi][yi] = GetNeighbors(l, side, xi, yi);
    //кэш координат соседних клеток
    }
    }
    }

    for(short i=0; i<m; i++) {
    for(short side=0; side<SIDENUM; side++) {
    for(short xi=0; xi<l; xi++) {
    for(short yi=0; yi<l; yi++) { //перебор всех клеток
    LongNum neighbor_sum;
    for(auto e: nbs[side][xi][yi].n) { //перебор всех соседей
    neighbor_sum.add(cubes[flag][e.side][e.x][e.y]);
    //сложение количества путей ко всем соседям на предыдущем шаге
    }
    cubes[!flag][side][xi][yi] = neighbor_sum;
    //запись получившейся суммы в клетку
    }
    }
    }
    flag = !flag; //замена местами массива для предыдущего шага и нынешнего
    }
    cubes[flag][1][l/2][l/2].print();
    //вывод количества путей к центру соседней грани на m-ом шаге
    }
     
    1. oriole Автор темы
      dragoniil, та не , я видел это, это кубы какие-то
Top
Загрузка...