2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3  След.
 
 Re: Задача вроде бы на Минимальные Остовные Деревья
Сообщение06.02.2015, 19:51 


10/05/13
251
sqribner48 в сообщении #974664 писал(а):
Спасибо. А исходный файл с входными данными задачи там выложен? Хотелось бы узнать какой граф $G$ разреженный или нет.
Сейчас мне показалось, что эта задача сводится к нахождению всех подграфов, у которых удвоенная сумма весов внутренних ребер не меньше чем сумма весов "выходящих наружу" ребер.
P.S. рисунки получились какие-то обрезанные по краям.


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

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

-- 06.02.2015, 21:55 --

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

 Профиль  
                  
 
 Re: Задача вроде бы на Минимальные Остовные Деревья
Сообщение06.02.2015, 20:17 
Заслуженный участник


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

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

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

 Профиль  
                  
 
 Re: Задача вроде бы на Минимальные Остовные Деревья
Сообщение06.02.2015, 20:25 


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

 Профиль  
                  
 
 Re: Задача вроде бы на Минимальные Остовные Деревья
Сообщение06.02.2015, 20:27 
Заслуженный участник


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

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

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

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

 Профиль  
                  
 
 Re: Задача вроде бы на Минимальные Остовные Деревья
Сообщение06.02.2015, 21:02 


13/05/14
476
sup в сообщении #974692 писал(а):
Надо думать, здесь речь идет о вершинах реберного графа.

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

(Оффтоп)

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

 Профиль  
                  
 
 Re: Задача вроде бы на Минимальные Остовные Деревья
Сообщение06.02.2015, 21:14 
Заслуженный участник


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

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

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

 Профиль  
                  
 
 Re: Задача вроде бы на Минимальные Остовные Деревья
Сообщение06.02.2015, 21:27 


13/05/14
476

(Оффтоп)

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

 Профиль  
                  
 
 Re: Задача вроде бы на Минимальные Остовные Деревья
Сообщение06.02.2015, 22:56 


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

У меня появилась идейка решения, и я ее реализовал на С++, для 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 - количесто ребер.

 Профиль  
                  
 
 Re: Задача вроде бы на Минимальные Остовные Деревья
Сообщение07.02.2015, 07:40 
Заслуженный участник


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

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

 Профиль  
                  
 
 Re: Задача вроде бы на Минимальные Остовные Деревья
Сообщение07.02.2015, 09:31 


01/12/11

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

 Профиль  
                  
 
 Re: Задача вроде бы на Минимальные Остовные Деревья
Сообщение07.02.2015, 11:50 


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

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

 Профиль  
                  
 
 Re: Задача вроде бы на Минимальные Остовные Деревья
Сообщение07.02.2015, 14:41 


13/05/14
476
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$ в графе могут быть клики разной мощности.

 Профиль  
                  
 
 Re: Задача вроде бы на Минимальные Остовные Деревья
Сообщение07.02.2015, 16:01 


01/12/11

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

 Профиль  
                  
 
 Re: Задача вроде бы на Минимальные Остовные Деревья
Сообщение07.02.2015, 17:07 


01/12/11

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

 Профиль  
                  
 
 Re: Задача вроде бы на Минимальные Остовные Деревья
Сообщение07.02.2015, 17:26 


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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 33 ]  На страницу Пред.  1, 2, 3  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group