7413. Сумма на дереве наоборот

В задаче “2157 Сумма для заданного дерева” следует найти суммарную длину всех путей в дереве.

Сейчас мы предлагаем Вам решить обратную задачу. Задана матрица расстояний между всеми вершинами дерева с n вершинами. Необходимо определить, может ли эта матрица быть матрицей попарных расстояний между всеми вершинами взвешенного дерева. Все веса ребер дерева должны быть натуральными числами.

Вход. Первая строка содержит размер матрицы n (1 ≤ n ≤ 1000). Далее следует матрица расстояний: в n строках расположены n целых неотрицательных чисел, не превосходящих 10⁹ - расстояния между парами вершин.

Выход. Вывести YES, если такое дерево существует, и NO иначе.

Пример входа	Пример выхода
3 0 5 1 5 0 6 1 6 0	YES

РЕШЕНИЕ

минимальный остов + поиск в глубину

Анализ алгоритма

На главной диагонали матрицы должны находиться нули. Все остальные элементы должны быть ненулевыми. Матрица должна быть симметричной.

Рассмотрим минимальное ненулевое расстояние, присутствующее в матрице. Тогда оно должно быть обязательно между двумя соседними вершинами. Объединим эти две вершины в одно множество. Рассмотрим k-ое минимальное расстояние в матрице. Пусть оно находится между вершинами u и v. Если эти две вершины еще находятся в разных множествах, то u и v следует соединить ребром соответствующего веса, объединив при этом соответствующие множества.

Построим минимальный остов из имеющихся расстояний, используя алгоритм Крускала (систему непересекающихся множеств). Далее за O(n²) найдем расстояния между всеми парами вершин, например, запустив поиск в глубину из каждой вершины. Эти расстояния должны совпадать со значениями, заданными во входной матрице.

Реализация алгоритма

Объявим глобальные массивы.

#define MAX 2010

int mas[MAX], depth[MAX], dist[MAX];

int m[MAX][MAX];

Объявим структуру данных ребро, соединяющее вершины u и v и имеющего вес w. Определим компаратор упорядочивания ребер по весу.

struct edge

{

int u, v, w;

edge() : u(0), v(0), w(0) {}

edge(int u, int v, int w) : u(u), v(v), w(w) {}

int operator<(edge &e)

{

return w < e.w;

}

};

Сортировать ребра в алгоритме Крускала будем в векторе e. Список смежности полученного взвешенного дерева храним в векторе пар g.

vector<edge> e;

vector<pair<int,int> > g[MAX];

Для ускорения работы реализуем функции Repr и Union с эвристиками сжатия пути и объединения по рангу на основе глубины деревьев.

int Repr(int n)

{

if (n == mas[n]) return n;

return mas[n] = Repr(mas[n]);

}

Функция Union возвращает 1, если ребро (u, v) веса w входит в остов.

int Union(int u, int v, int w)

{

int u1 = Repr(u), v1 = Repr(v);

if (u1 == v1) return 0;

if (depth[u1] < depth[v1]) swap(u1,v1);

mas[v1] = u1;

if (depth[u1] == depth[v1]) depth[u1]++;

Ребро (u, v) веса w входит в остов. Добавляем его в искомое дерево.

g[u].push_back(make_pair(v,w));

g[v].push_back(make_pair(u,w));

return 1;

}

Поиск в глубину из вершины v. Вычисление расстояний (кратчайших, так как поиск совершается на дереве) до вершин от стартовой.

void dfs(int v)

{

int i, to, w;

for(i = 0; i < g[v].size(); i++)

{

to = g[v][i].first;

w = g[v][i].second;

if (dist[to] == -1)

{

dist[to] = dist[v] + w;

dfs(to);

}

}

}

Читаем входную матрицу. Проверяем на этапе чтения, что:

· на диагонали должны находиться нули

· остальные числа должны быть ненулевыми

· матрица должна быть симметричной

Функция ReadGraph возвращает 0, если ответ будет точно NO.

int ReadGraph(void)

{

int i, j;

for(i = 1; i <= n; i++)

for(j = 1; j <= n; j++)

{

scanf("%d",&m[i][j]);

if (i == j)

{

if (m[i][i]) return 0; else continue;

}

if (!m[i][j]) return 0;

if (i <= j) continue;

if (m[i][j] != m[j][i]) return 0;

edge temp (i,j,m[i][j]);

e.push_back(temp);

}

return 1;

}

Основная часть программы. Читаем входную матрицу.

scanf("%d",&n);

if(!ReadGraph())

{

printf("NO\n");

return 0;

}

Сортируем ребра по возрастанию весов.

sort(e.begin(), e.end());

Инициализация системы непересекающихся множеств. Каждый представитель множества указывает сам на себя.

for(i = 1; i <= n; i++) mas[i] = i;

memset(depth,0,sizeof(depth));

Запускаем алгоритм Крускала, пока в минимальный остов не занесем n – 1 ребро.

c = n;

for(i = 0; i < e.size(); i++)

{

if (Union(e[i].u,e[i].v,e[i].w)) c--;

if (c == 1) break;

}

Из i-ой вершины запускаем поиск в глубину, вычисляя расстояния от ее до всех остальных вершин в массиве dist.

for(i = 1; i <= n; i++)

{

memset(dist,-1,sizeof(dist));

dist[i] = 0;

dfs(i);

Найденные расстояния должны совпадать с данными во входной матрице.

for(j = 1; j <= n; j++)

if (m[i][j] != dist[j])

{

printf("NO\n");

return 0;

}

}

Искомое дерево существует.

printf("YES\n");