Задача вроде бы на Минимальные Остовные Деревья

[frankenstein]

sqribner48 в сообщении #974664 писал(а):

Спасибо. А исходный файл с входными данными задачи там выложен? Хотелось бы узнать какой граф $G$ разреженный или нет.
Сейчас мне показалось, что эта задача сводится к нахождению всех подграфов, у которых удвоенная сумма весов внутренних ребер не меньше чем сумма весов "выходящих наружу" ребер.
P.S. рисунки получились какие-то обрезанные по краям.

Эта задача из онлайн тестирующей системы. Они не дадут вам свой тестовый пример, а просто протестируют ваше решение и скажут прошло оно все тесты или нет. Эта система подготовки к олимпиадам.

Максимальный случай это полный граф с 5000 вершинами.

-- 06.02.2015, 21:55 --

sup
Какова будет сложность алгоритма вашего решения?

[sup]

Если считать совсем примитивно, то $O(n^4)$. Цикл по ребрам - $O(n^2)$. И для каждого ребра работы $O(n^2)$. Это весьма грубая оценка для полного графа. В реальности должно быть существенно меньше. Куча ребер не сможет дать старт кандидатам. Возможно, стоит подумать о порядке рассмотрения стартовых ребер. Например, сначала все ребра отсортировать.

-- Пт фев 06, 2015 23:19:55 --

Можно попробовать на случайных графах поэкспериментировать и набрать статистику.

[frankenstein]

Эта олимпиадная задача и для нее есть простое решение как обычно и бывает.
Ну $O(n^4)$ это слишком, даже $O(n^3)$ не годится.
При $n = 5000$ это будет очень долго.
Ограничение по времени 3 сек.

[sup]

Ну да, уже можно гарантировать,что не более $O(n^3)$. Стартовых ребер не более $n/2$.
Ну действительно. Рассмотрим какую-нибудь вершину. Среди всех ребер ей инцидентных, только одно (максимальное) может (хотя и не факт) дать старт поиску.
Значит все будет "хорошо"

-- Пт фев 06, 2015 23:29:53 --

frankenstein в сообщении #974725 писал(а):

Эта олимпиадная задача и для нее есть простое решение как обычно и бывает.
Ну $O(n^4)$ это слишком, даже $O(n^3)$ не годится.

Вы слишком буквально воспринимаете все эти оценки. Это очень грубые оценки самого худшего случая.

[sqribner48]

sup в сообщении #974692 писал(а):

Надо думать, здесь речь идет о вершинах реберного графа.

Да, именно об этом я и говорил. То есть я сделал предложение использовать вместо исходного графа его реберный граф. Мне показалось, что в случае графа $G$ с небольшим числом ребер этот вариант более удобен.

(Оффтоп)

frankenstein
Спасибо, что просветили меня про тестирование программ на олимпиаде. Не знал, потому что в таких олимпиадах не участвовал.

[sup]

Я не думаю, что дело дойдет прям-таки до явного представления реберного графа. А вот использовать его концептуально - почему бы и нет. Хотя, как мне кажется, все достаточно прямолинейно. Впрочем, похоже что ТС "загоревал" по поводу сложности алгоритма
Мне просто лень набрать статистику. Но я в сущности убежден, что указанный алгоритм даст "нормальный" результат.

-- Сб фев 07, 2015 00:23:13 --

Ну, можно еще немного усилить наши рассуждения. В каждой вершине $v$ найдем ребро $E_v$ с максимальным весом. Далее, всякое ребро $(a,b)$ может входить в какое-то множество $B$ только лишь при условии, что $B$ содержит и $E_a$ и $E_b$.
По-видимому, надо строить $B$ только на ребрах $E_v$. А их "мало". Вполне рабочая идея.

[sqribner48]

(Оффтоп)

sup
Согласен с Вами. Вы уже дали достаточно много ценных идей и оценку сложности.
frankenstein осталось только реализовать.

[frankenstein]

Да, идеи отличные, в этом то и дело. Кажется вот что-то не то.
Не должна эта задача решаться так отлично от других из того же раздела
задач про минимальные остовы.

У меня появилась идейка решения, и я ее реализовал на С++, для test caseов
из условия задачи ответы верные, да и не нашел пока тестов на которых решение валится.
Но системное тестирование решение не прошло.
Тут нужен какой-то тест на котором он валится, если не найду такой, попробую реализовать
идею sup.

Идея такова:
1. Сгруппируем ребра по весам (Т. к. диапазон значений весов небольшой можно создать
массив списков, ну, это я отвлекся к реализации).
2. Представим граф без его ребер, очевидно что каждая вершина - компонента связности.
3. Добавим группу ребер с максимальным весом, после чего некоторые компоненты связности объединятся.
4. Посчитаем сумму мощностей каждой, возникшей в результате шага 3, компоненты связности (очевидно, что каждая из них - кандидат).
5. Удалим добавленную группу ребер и перейдем к шагу 3, если ребер не осталось переходим к шагу 6.
6. Конец алгоритма.

Я использовал Стуркутуры Данных UFDS для определения новых возникших компонент связности.
Здесь представлен код:

Используется синтаксис C++

#include <set>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <cmath>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstring>
#include <climits>
#include <iomanip>
#include <iostream>
#include <algorithm>

#define INF INT_MAX-1
#define SQR(x) ((x)*(x))

using namespace std;

#define vertex_sz_MAX   5001
#define edge_w_MAX              100001

/* ufds */
namespace {
        int parent[vertex_sz_MAX];
        int size[vertex_sz_MAX];

        void init_set() {
                for (int i = 0; i < vertex_sz_MAX; ++i) {
                        parent[i] = i;
                        size[i] = 1;
                }
        }
        int find_set(int x) {
                return x == parent[x] ? x : parent[x] = find_set(parent[x]);
        }
        /* keeps track about newly formed components */
        void join_set(int x, int y, set<int> & new_comp) {
                x = find_set(x);
                y = find_set(y);

                if (x == y)
                        return;

                if (size[x] > size[y]) {
                        parent[y] = x;
                        size[x] += size[y]; new_comp.insert(x);
                        size[y] = 0; new_comp.erase(y);
                } else {
                        parent[x] = y;
                        size[y] += size[x]; new_comp.insert(y);
                        size[x] = 0; new_comp.erase(x);
                }
        }
}

int vertex_sz, edges_sz, w_max;
list<pair<int, int> > edges[ edge_w_MAX ];

int solve() {
        init_set();

        set<int> new_comp;
        int count = 0;
        for (int w = w_max; w >= 1; --w) {
                new_comp.clear();

                /* add edges with same weights */
                for (list<pair<int, int> >::iterator it = edges[w].begin(); it != edges[w].end(); ++it) {
                        join_set(it->first, it->second, new_comp);
                }

                for (set<int>::iterator it = new_comp.begin(); it != new_comp.end(); ++it) {
                        count += size[*it];
                }
        }

        return count;
}

int main() {
        int test_n, x, y, w;
        cin >> test_n;

        while (test_n--) {
                /* prepare stage */
                w_max = 0;
                for (int i = 0; i < edge_w_MAX; ++i)
                        edges[i].clear();

                /* input stage */
                cin >> vertex_sz >> edges_sz;
                while (edges_sz--) {
                        cin >> x >> y >> w;
                        w_max = max(w, w_max);
                        edges[w].push_back(make_pair(x, y));
                }

                /* solve and output */
                cout << solve() << endl;
        }

        return 0;
}
 

-- 07.02.2015, 01:07 --

Сложность алгоритма $O(m)$, где m - количесто ребер.

[sup]

Шаг 5 вызывает вопросы. Что такое "удалим добавленную группу"?
Сложность $O(m)$ то же выглядит несколько оптимистичной. На каждом шагу надо проверять склейку кластеров.

Но в целом, может Вы и правы, насчет остовного дерева. Т.е. по сути это похоже на алгоритм Крускала - растущий лес. Единственное, что надо доказать, что других графов-кандидатов (кроме тех, что получатся) не существует. Вот это надо бы доказать.
В сущности, это тот самый алгоритм, что я и описывал, только разные циклы слиты в одну схему (ну и сложность у него за счет этого лучше).

[Skeptic]

Минимальный кандидат - это линейный граф, у которого внутреннее ребро имеет наибольший вес. Упорядочим рёбра по весу. Получим возрастающую числовую последовательность.
Рассмотрим полный граф. Число минимальных кандидатов $C_n^3$.
Рассуждая подобным образом для кандидатов, разной мощности, получим общее число кандидатов $\sum_{i=3}^n C_n^i$. Примерно, как-то так.

[frankenstein]

Подскажите что такое линейный граф? Это дерево?

У меня сейчас такая ситуация.
Либо решение неверно в корне и надо все переделывать.
Либо найти тот тест на котором он валится и исправить мелкую ошибку в коде (которая уж точно должна быть).

[sqribner48]

Skeptic в сообщении #974904 писал(а):

Минимальный кандидат - это линейный граф, у которого внутреннее ребро имеет наибольший вес.

Имеется большое количество определений линейного графа

(Оффтоп)

например:
1. Линейный граф $L(A)$ графа $A$ имеет вершину, соответствующую каждому ребру графа $A$, и две вершины $L(A)$ соединены ребром, если и только если соответствующие ребра графа $A$ имеют общую вершину (это наш родной реберный граф)
2. Направленным или линейным графом ( графом сигнала, диаграммой прохождения сигнала) называют совокупность узлов и соединяющих их ветвей, стрелки на которых указывают направление передачи сигнала ( воздействия) от одного узла к другому.
3. Сеть ( или линейный граф) состоит из множества узлов ( или вершин, точек) и множества дуг ( или ребер, звеньев), соединяющих различные пары узлов.
4. Граф, отражающий систему линейных уравнений, называется линейным.
5. Линейный граф - упорядоченное множество связных частей многоугольного графа (Салий В.Н)
6. Линейный граф, если говорить не строго, это совокупность точек и совокупность линий (или пар точек), с помощью которых изображаются соединения точек (Дж. Риордан).

какое из них выбрать?

Skeptic в сообщении #974904 писал(а):

Рассмотрим полный граф. Число минимальных кандидатов $C_n^3$.

А почему не $C_n^2$ или не $C_n^4$ и т. д.? Ведь при большой величине $n$ в графе могут быть клики разной мощности.

[Skeptic]

Линейный граф - это граф, рёбра которого можно вытянуть в линию.
Плоский граф - это граф, который можно расположить на плоскости без пересечения рёбер.
$N$-мерный граф - это, понятно, какой граф.
Минимальный кандидат - это граф с одним внутренним ребром и двумя граничными. Поэтому сочетание по три элемента, а не по два.
Приведённые выражения - это оцека сверху множества кандидатов.

[Skeptic]

Уточнение: $n$ в выражениях - это число рёбер.

[frankenstein]

Если следовать вашей оценке количества кандидатов, то в данной задаче при максимальном количестве вершин 5000,
ответ не поместится в 31 бита. Я заменил переменную счетчик на 63 битную переменную, но все равно валится решение
на системных тестах, (блин, почему они не показывают тесты?).

Интересно, какой же тест валит решение!