Олег Громазин сильно помог с алгоритмом определения порядка оплаты и регистрации налоговых накладных.

1. Строим направленный взвешенный граф, где вершины это компании, ребра это операции перевода денег, вес ребра — общая сумма НН, которое должна зарегистрировать компания из которой ребро выходит. Граф связанный, если у него есть не связанные области, то это просто два независимых графа.

2. Каждой вершине присваиваем значение условного баланса = 0.

3. Для каждой не помеченной как удаленной вершины считаем сумму весов ребер входящих в неё.

4. Выбираем вершину с минимальной суммой. Помечаем её как удаленную. Если их несколько, выбираем случайную.

5. Смотрим на ребра которые выходят из неё. Добавляем к условному балансу вершин в которые «входят» эти ребра величину веса. Обнуляем вес ребер.

6. Если условный баланс вершины больше чем сумма весов ребер выходящих из неё, повторяем для неё пункт 5.

7. Если остались ребра с не 0 весом, то повторяем с пункта 3.

Порядок оплаты это порядок пометки вершин как удаленные

Advertisements