Category Archives: D. Графы

Алгоритмы на графах

Задачи на графах

Опубликовано: 18/05/2016

-= заготовка статьи =- Общим для задач на графах является необходимость их как-то хранить в программе. Для хранения графа [latex] G \left( V, E \right), |V| = n, |E| = m [/latex] в разных случаях используют различные методы. Наиболее популярны из них: Матрица смежности [latex] O \left( n^2 \right) [/latex] Матрица инцидентности [latex] O \left( … Continue reading →

e-olymp 1947. Конденсация графа

25/05/2017 by Валентина Андриеш

Условие задачи:

Для заданного ориентированного графа найти количество ребер в его конденсации.

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

Конденсация графа не содержит кратных ребер.

Входные данные:

Первая строка содержит два натуральных числа n и m (n ≤ 10000, m ≤ 100000) — количество вершин и ребер графа соответственно. Каждая из следующих m строк содержит описание ребра графа. Ребро номер i описывается двумя натуральными числами [latex]b_{i}[/latex], [latex]e_{i}[/latex](1 ≤ [latex]b_{i}[/latex], [latex]e_{i}[/latex] ≤ n) — номерами начальной и конечной вершины соответственно. В графе могут присутствовать кратные ребра и петли.

Выходные данные:

Количество ребер в конденсации графа.

Тесты:

Входные данные		Выходные данные
4	4	2
2	1
3	2
2	3
4	3
6	9	1
1	2
2	4
4	1
4	2
3	2
2	6
3	5
5	3
6	2

#include <iostream>
#include <vector>
#include <set>

using namespace std;

struct vertex{          
    int used,colour;
    vector<int>graph,graph_transposed;
};

void dfs_g(int v, vector<vertex>&components, vector<int>&list){
    components[v].used = 1;
    for (int i = 0; i < components[v].graph.size(); i++){
        if(components[components[v].graph[i]].used!=1) dfs_g(components[v].graph[i],components,list);
    }
    list.push_back(v);
}

void dfs_tg(int v, int color, vector<vertex>&components){
    components[v].used=2;
    components[v].colour=color;
    for (int i=0; i<components[v].graph_transposed.size(); i++){
        if (components[components[v].graph_transposed[i]].used != 2)dfs_tg(components[v].graph_transposed[i],color,components);
    }
}

int main(){
    int n,m,color=0,answer=0;
    cin>>n>>m;
    vector<int>list(n);
    vector<vertex>components(n);
    set<int>ribs[10000];
    for(int i=0; i<m; i++){
        int a,b;
        cin>>a>>b;
        components[a-1].graph.push_back(b-1);
        components[b-1].graph_transposed.push_back(a-1);
    }

    for (int i=0; i<n; i++){
        if (components[i].used!=1)dfs_g(i,components,list);
    }
    for (int i=list.size()-1; i>=0; i--){
        if (components[list[i]].used != 2){
            dfs_tg(list[i], color, components);
            color++;
        }
    }
    for(int i=0; i<n; i++){
        for(int j=0; j<components[i].graph.size(); j++){
            if(components[i].colour!=components[components[i].graph[j]].colour){
                ribs[components[i].colour].insert(components[components[i].graph[j]].colour);
            }
        }
    }
    for(int i=0; i<10000; i++)answer+=ribs[i].size();
    cout<<answer;
    return 0;
}

#include <iostream>

#include <vector>

#include <set>

using namespace std;

struct vertex{

int used,colour;

vector<int>graph,graph_transposed;

};

void dfs_g(int v, vector<vertex>&components, vector<int>&list){

components[v].used = 1;

for (int i = 0; i < components[v].graph.size(); i++){

if(components[components[v].graph[i]].used!=1) dfs_g(components[v].graph[i],components,list);

}

list.push_back(v);

}

void dfs_tg(int v, int color, vector<vertex>&components){

components[v].used=2;

components[v].colour=color;

for (int i=0; i<components[v].graph_transposed.size(); i++){

if (components[components[v].graph_transposed[i]].used != 2)dfs_tg(components[v].graph_transposed[i],color,components);

}

int main(){

int n,m,color=0,answer=0;

cin>>n>>m;

vector<int>list(n);

vector<vertex>components(n);

set<int>ribs[10000];

for(int i=0; i<m; i++){

int a,b;

cin>>a>>b;

components[a-1].graph.push_back(b-1);

components[b-1].graph_transposed.push_back(a-1);

}

for (int i=0; i<n; i++){

if (components[i].used!=1)dfs_g(i,components,list);

}

for (int i=list.size()-1; i>=0; i--){

if (components[list[i]].used != 2){

dfs_tg(list[i], color, components);

color++;

}

for(int i=0; i<n; i++){

for(int j=0; j<components[i].graph.size(); j++){

if(components[i].colour!=components[components[i].graph[j]].colour){

ribs[components[i].colour].insert(components[components[i].graph[j]].colour);

}

for(int i=0; i<10000; i++)answer+=ribs[i].size();

cout<<answer;

return 0;

}

Описание решения задачи:

Компонентой сильной связности называется такое подмножество вершин C, что любые две вершины этого подмножества достижимы друг из друга. Отсюда следует, что конденсация это граф, получаемый из исходного графа сжатием каждой компоненты сильной связности в одну вершину. Отсюда имеем структуру [latex]vertex[/latex]. Основным фундаментом данного алгоритма является следующая теорема: Пусть [latex]C[/latex] и [latex]{C}'[/latex] — две различные компоненты сильной связности, и пусть в графе конденсации между ними есть ребро ([latex]C[/latex],[latex]C'[/latex]). Тогда время выхода из [latex]C[/latex] будет больше, чем время выхода из [latex]{C}'[/latex]. Базируясь на этом, выполним серию обходов в глубину с помощью функции [latex]dfs[/latex] _ [latex]g[/latex], посещая весь граф. С визитом всех вершин графа,запоминаем для каждой время выхода, записывая это в созданный [latex]list[/latex]. Далее строится транспонированный граф. Запускаем серию обходов в глубину(функция [latex]dfs[/latex] _ [latex]tg[/latex]) этого графа в порядке, определяемом списком [latex]list[/latex] (а именно, в обратном порядке, т.е. в порядке уменьшения времени выхода). Каждое множество вершин, достигнутое в результате рекурсивного запуска обхода, и будет очередной компонентой сильной связности. Окрасим все вершины каждой сильной компоненты связности в один уникальный цвет, для этого зададим в структуре параметр [latex]colour[/latex]. Число цветов окраски будет равно количеству компонент сильной связности. Далее перебираем все ребра исходного графа. Если ребро соединяет вершины разного цвета, то оно принадлежит конденсации графа. Для каждого ребра ([latex]a[/latex], [latex]b[/latex]), для которого [latex]components[a].colour[/latex] [latex]≠[/latex] [latex]components[b].colour[/latex], занесем во множество [latex]ribs[/latex] данную пару. Количество элементов во множестве [latex]ribs[/latex] будет равняться числу ребер в конденсации графа.

Условие задачи
Код задачи на с++
Засчитанное решение на e-olymp

Related Images:

e-olimp 4852. Кратчайшее расстояние

27/06/2016 by Аня Шохина

Задача

Дан ориентированный граф. Найдите кратчайшее расстояние от вершины x до всех остальных вершин графа.

Входные данные

В первой строке содержатся два натуральных числа [latex]n[/latex] и [latex]x[/latex] [latex]\left ( 1\leq n\leq 1000,1\leq x\leq n \right )[/latex] — количество вершин в графе и стартовая вершина соответственно. Далее в [latex]n[/latex] строках по [latex]n[/latex] чисел — матрица смежности графа: в [latex]i[/latex]-ой строке на [latex]j[/latex]-ом месте стоит [latex]1[/latex], если вершины [latex]i[/latex] и [latex]j[/latex] соединены ребром, и [latex]0[/latex], если ребра между ними нет. На главной диагонали матрицы стоят нули.

Выходные данные

Выведите через пробел числа [latex]d_1,d_2,[/latex][latex]\ldots[/latex][latex],d_i[/latex], где [latex]d_i[/latex] равно[latex]-1[/latex], если путей между [latex]x[/latex] и [latex]i[/latex] нет, в противном случае это минимальное расстояние между [latex]x[/latex] и [latex]i[/latex].

Тесты

Входные данные	Выходные данные
3 1 0 1 0 0 0 0 0 0 0	0 1 -1
6 5 0 1 1 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 0	2 2 1 1 0 -1
3 1 0 1 0 1 0 1 0 1 0	0 1 2

Реализация

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    const int inf=4000; // задаем бесконечность 
    int n, start_position, x; // n-количество вершин,х используем для приема матрицы смежности 
    cin>>n>>start_position;
    start_position--; // в условии счет начинается с единицы, а в программе с нуля 
    vector <int> verges [1001]; //задаем массив векторов, где i-ый вектор содержит в себе номера вершин в которые можно попасть с i-ой вершины
    for (int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin>>x;
            if (x==1){
                verges[i].push_back(j);
            }
        }
    }
    bool *used = new bool [n];
    for (int i=0; i<n; i++){
        used[i]=false;
    }
    int *distances = new int [n]; //задаем массив расстояний, где i-ый элемент - это расстояние от исходной вершины до  i-ой
    for (int i=0; i<n; i++){
        distances[i]=inf; 
    }
    distances[start_position] = 0;
    for (int i=0; i<n; i++){ //ищем вершину с наименьшей длиной пути до заданной вершины 
        int minimum=inf;
        int position = 0;
        for (int j=0; j<n; j++){
            if (distances[j]<minimum && !used[j]){
                minimum=distances[j];
                position=j;
            }
        }
        used[position]=true; //запоминаем, что применили алгоритм для вершины 
        for (int i=0; i<verges[position].size(); i++){ // применяем алгоритм Дейкстры 
            distances[verges[position][i]] = min(distances[verges[position][i]], (distances[position]+1));
        }
    }
    for (int i=0; i<n; i++) {
        cout<<((distances[i]==inf)?-1:distances[i])<<" ";
    }
    return 0;
}

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

int main() {

const int inf=4000; // задаем бесконечность

int n, start_position, x; // n-количество вершин,х используем для приема матрицы смежности

cin>>n>>start_position;

start_position--; // в условии счет начинается с единицы, а в программе с нуля

vector <int> verges [1001]; //задаем массив векторов, где i-ый вектор содержит в себе номера вершин в которые можно попасть с i-ой вершины

for (int i=0; i<n; i++){

for(int j=0; j<n; j++){

cin>>x;

if (x==1){

verges[i].push_back(j);

}

bool *used = new bool [n];

for (int i=0; i<n; i++){

used[i]=false;

}

int *distances = new int [n]; //задаем массив расстояний, где i-ый элемент - это расстояние от исходной вершины до i-ой

for (int i=0; i<n; i++){

distances[i]=inf;

}

distances[start_position] = 0;

for (int i=0; i<n; i++){ //ищем вершину с наименьшей длиной пути до заданной вершины

int minimum=inf;

int position = 0;

for (int j=0; j<n; j++){

if (distances[j]<minimum && !used[j]){

minimum=distances[j];

position=j;

}

used[position]=true; //запоминаем, что применили алгоритм для вершины

for (int i=0; i<verges[position].size(); i++){ // применяем алгоритм Дейкстры

distances[verges[position][i]] = min(distances[verges[position][i]], (distances[position]+1));

}

for (int i=0; i<n; i++) {

cout<<((distances[i]==inf)?-1:distances[i])<<" ";

}

return 0;

}

Засчитанное решение на e-olimp.com

Код на ideone.com

Решение

Для решения данной задачи необходимо применить алгоритм Дейкстры . А именно, мы храним в массиве текущую длину наиболее короткого пути из заданной вершины во все остальные вершины графа. Положим, что изначально длина такого пути равна бесконечности ( при реализации просто используем достаточно большое число). А длина пути из заданной вершины до самой себя равна нулю. Обозначим, что вершина может быть помечена или не помечена. Изначально все вершины являются не помеченными. Далее выбираем вершину [latex]v[/latex] с наименьшей длиной пути до заданной вершины и помечаем ее. Тогда просматриваем все ребра, исходящие из вершины [latex]v[/latex]. Пусть эти ребра имеют вид [latex]\left ( v,t_0 \right )[/latex]. Тогда для каждой такой вершины [latex]t_0[/latex] пытаемся найти наиболее коротки путь из заданной вершины. После чего снова выбираем еще не помеченную вершину и проделываем вышеописанный алгоритм снова до тех пор, пока не останется не помеченных вершин. Найденные расстояния и будут наименьшими.

Related Images:

e-olymp 1108. Червячные дыры

06/06/2016 by Грешилов Константин

Условие:

В 2163 году были обнаружены червячные дыры. Червячная дыра представляет собой тоннель сквозь пространство и время, соединяющий две звездные системы. Эти дыры имеют следующие свойства:

Червячные дыры являются односторонними.
Время путешествия по любому тоннелю равно нулю.
Червячная дыра имеет два конца, каждый из которых находится в звездной системе.
Звездная система в своих границах может иметь несколько концов червячных дыр.
По некоторой неизвестной причине начиная с нашей Солнечной системы всегда можно достигнуть любую другу звездную систему перемещаясь некоторой последовательностью червячных дыр (возможно, это потому что Земля является центром универсума).
Между любой парой звездных систем существует не более одной червячной дыры в любом из направлений.
Оба конца червячной дыры не могут находиться в одной звездной системе.
Каждая червячная дыра перемещает путешественника на определенное константное количество лет вперед или назад. Например, одна дыра может переместить на 15 лет в будущее, а другая на 42 года в прошлое.

Известный физик, живущий на Земле, хочет использовать червячные дыры для исследования теории Большого Взрыва. Поскольку двигатель искривления пространства еще не изобретен, невозможно напрямую путешествовать между звездными системами. Однако это можно делать при помощи червячных дыр.

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

Входные данные

Первая строка содержит количество звездных систем n (1 ≤ n ≤ 1000) и количество червячных дыр m (0 ≤ m ≤ 2000). Звездные системы пронумерованы от 0 (наша солнечная система) до n — 1. Каждая червячная дыра описывается в отдельной строке и содержит три целых числа x, y и t. Эти числа указывают на возможность передвижения из звездной системы с номером x в звездную систему с номером y, при этом время изменяется на t (-1000 ≤ t ≤ 1000) лет.

Выходные данные

Cтрока содержит информацию, возможно ли в заданном множестве систем попасть в минус бесконечность во времени используя червячные дыры. Выводить следует строку «possible» или «not possible«.

Тесты:

Входные данные	Выходные данные
3 3 0 1 1000 1 2 15 2 1 -42	possible
4 4 0 1 10 1 2 20 2 3 30 3 0 -60	not possible
3 3 0 1 -100 1 2 1 2 1 0	not possible

Решение:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct canal {
    int x, y, t;
};
 
int main() {
    int n, m;
    vector <canal> canals;
    cin >> n >> m;
    canal r;
    for (int i=0; i < m; i++)
    {
        cin >> r.x >> r.y >> r.t;
        canals.push_back(r);
    }
    const int INF = 2000000;
    vector <int> distance (n);
    int x;
    for (int i = 0; i < n; i++) {
        x = -1;
        for (int j = 0; j < m; j++)
            if (distance[canals[j].y] > distance[canals[j].x] + canals[j].t) {
                distance[canals[j].y] = max (-INF, distance[canals[j].x] + canals[j].t);
                x = canals[j].y;
            }
    }
 
    if (x == -1)
        cout << "not possible" << endl;
    else {
        cout << "possible" << endl;
    }
    return 0;
}

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

struct canal {

int x, y, t;

};

int main() {

int n, m;

vector <canal> canals;

cin >> n >> m;

canal r;

for (int i=0; i < m; i++)

{

cin >> r.x >> r.y >> r.t;

canals.push_back(r);

}

const int INF = 2000000;

vector <int> distance (n);

int x;

for (int i = 0; i < n; i++) {

x = -1;

for (int j = 0; j < m; j++)

if (distance[canals[j].y] > distance[canals[j].x] + canals[j].t) {

distance[canals[j].y] = max (-INF, distance[canals[j].x] + canals[j].t);

x = canals[j].y;

}

if (x == -1)

cout << "not possible" << endl;

else {

cout << "possible" << endl;

}

return 0;

}

Описание решения:

Решение данной задачи сводится к нахождению отрицательного цикла в ориентированном графе. Необходимо воспользоваться алгоритмом Форда-Беллмана. Создадим вектор на [latex]n[/latex] элементов и заполним его нулями. Алгоритм основан на том, что если в графе размерностью [latex]n[/latex] элементов нет отрицательных циклов, то после [latex]n-1[/latex] прохождения, изменения в массива кратчайших расстояний не будет. Поэтому, будем выполнять следующее [latex]n[/latex] раз:

Возьмем первое ребро из вектора [latex]canals[/latex], и проведем сравнение: если исходная длина пути конца данного ребра из исходного вектора [latex]distance[/latex] больше, чем сумма длины пути начала вектора и стоимости прохода по данному ребру [latex]canals[].t[/latex], то изменим в векторе [latex]distance[/latex] элемент с номером конца исходного ребра, и изменим индикатор изменений [latex]x[/latex], чтобы показать, что в ходе данного прохода были внесены изменения.
Переходим к следующему ребру.

Если после во время последнего прохода ни разу не была изменена переменная [latex]x[/latex], то это значит, что в графе нет циклов отрицательной длины, и тогда выводим «not possible». Иначе, выводим «possible».

Засчитанное решение на e-olymp.com.

Код решения на ideone.com.

Related Images:

e-olymp 1948. Топологическая сортировка

06/06/2016 by Грешилов Константин

Условие:
Дан ориентированный невзвешенный граф. Необходимо топологически отсортировать его вершины.

Входные данные

В первой строке содержатся количество вершин [latex]n[/latex] (1 ≤ [latex]n[/latex] ≤ 100000) и количество рёбер [latex]m[/latex] (1 ≤[latex]m[/latex] ≤ 100000) в графе. В следующих [latex]m[/latex] строках перечислены рёбра графа, каждое из которых задаётся парой чисел — номерами начальной и конечной вершины.

Выходные данные

Вывести любую топологическую сортировку графа в виде последовательности номеров вершин. Если граф невозможно топологически отсортировать, то вывести -1.

Тесты:

Входные данные	Выходные данные
6 6 1 2 3 2 4 2 2 5 6 5 4 6	4 6 3 1 2 5
2 2 1 2 2 1	-1
4 5 1 2 1 3 3 4 2 4 1 4	1 3 2 4
4 5 1 2 1 3 3 4 2 4 4 1	-1

Решение:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool cyclic (int v, int &cycle_st, vector <int> *graph, vector <int> &color ) { //проверка графа на цикличность
    color[v] = 1;
    for (size_t i = 0; i < graph[v].size(); ++i) {
        int to = graph[v][i];
        if (color[to] == 0) { //если в вершину не входили ни разу
            if (cyclic (to, cycle_st, graph,  color))  return true;
        }
        else if (color[to] == 1) { //если в указанную вершину ранее входили, то значит, что найден цикл
            cycle_st = to; // и меняем значение индикатора 
            return true; 
        }
    }
    color[v] = 2; //указываем, что в вершину больше ни разу входить не будем
    return false;
}
void dfs (int v, vector <int> *graph, vector<bool> &used, vector <int> &answer) {
    used[v] = true; //указываем, что использовали данную вершину
    for (int i=0; i < graph[v].size(); i++) {
        int to = graph[v][i]; //по списку проходим по всем вершинам, к которым можно пройти от вершины v
        if (!used[to])//и если вершину не рассматривали, то применяем алгоритм поиска в глубину для неё
            dfs (to, graph, used, answer);
    }
    answer.push_back (v+1); // заносим вершину в вектор, хранящий результат
}
 
void topological_sort(int n, vector <int> *graph, vector<bool> &used, vector <int> &answer) {
    for (int i = 0; i < n; i++) //указываем, что ни одна вершина не была использована
        used[i] = false;
    for (int i = 0; i < n; i++)
        if (!used[i]) //если в ходе предыдущий операций вершина не использовалась
            dfs (i, graph, used, answer); // то вызываем для неё алгоритм поиска в глубину
    reverse (answer.begin(), answer.end());
}

int main() {
    int n, m; // число вершин и ребер
    cin >> n >> m;
    int a, b;
    vector <int> graph[100001]; // граф
    vector <bool> used (n);
    vector<int> answer;
    vector<int> color (n,0); //массив, хранящий кол-во посещений для данной вершины.
    int cycle_st = -1;
    for (int i = 0; i < m; i++){
            cin >> a >> b;
            graph[a-1].push_back(b-1);
        }
    for (int i = 0; i < n; i++){
        if (cyclic(i, cycle_st, graph, color)) //проверка графа на ацикличность
            break;
    }
    if (cycle_st != -1){ 
        cout << "-1";
    }
    else{
        topological_sort(n, graph, used, answer);
        for (int i = 0; i < answer.size(); i++)
        {
            cout << answer[i] << " "; 
        }
        cout << endl;
    }
    return 0;
}

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

bool cyclic (int v, int &cycle_st, vector <int> *graph, vector <int> &color ) { //проверка графа на цикличность

color[v] = 1;

for (size_t i = 0; i < graph[v].size(); ++i) {

int to = graph[v][i];

if (color[to] == 0) { //если в вершину не входили ни разу

if (cyclic (to, cycle_st, graph, color)) return true;

}

else if (color[to] == 1) { //если в указанную вершину ранее входили, то значит, что найден цикл

cycle_st = to; // и меняем значение индикатора

return true;

}

color[v] = 2; //указываем, что в вершину больше ни разу входить не будем

return false;

}

void dfs (int v, vector <int> *graph, vector<bool> &used, vector <int> &answer) {

used[v] = true; //указываем, что использовали данную вершину

for (int i=0; i < graph[v].size(); i++) {

int to = graph[v][i]; //по списку проходим по всем вершинам, к которым можно пройти от вершины v

if (!used[to])//и если вершину не рассматривали, то применяем алгоритм поиска в глубину для неё

dfs (to, graph, used, answer);

}

answer.push_back (v+1); // заносим вершину в вектор, хранящий результат

}

void topological_sort(int n, vector <int> *graph, vector<bool> &used, vector <int> &answer) {

for (int i = 0; i < n; i++) //указываем, что ни одна вершина не была использована

used[i] = false;

for (int i = 0; i < n; i++)

if (!used[i]) //если в ходе предыдущий операций вершина не использовалась

dfs (i, graph, used, answer); // то вызываем для неё алгоритм поиска в глубину

reverse (answer.begin(), answer.end());

}

int main() {

int n, m; // число вершин и ребер

cin >> n >> m;

int a, b;

vector <int> graph[100001]; // граф

vector <bool> used (n);

vector<int> answer;

vector<int> color (n,0); //массив, хранящий кол-во посещений для данной вершины.

int cycle_st = -1;

for (int i = 0; i < m; i++){

cin >> a >> b;

graph[a-1].push_back(b-1);

}

for (int i = 0; i < n; i++){

if (cyclic(i, cycle_st, graph, color)) //проверка графа на ацикличность

break;

}

if (cycle_st != -1){

cout << "-1";

}

else{

topological_sort(n, graph, used, answer);

for (int i = 0; i < answer.size(); i++)

{

cout << answer[i] << " ";

}

cout << endl;

}

return 0;

}

Описание решения:

Для решения данной задачи необходимо было воспользоваться алгоритмом топологической сортировки, посредством поиcка в глубину. Чтобы применить данный алгоритм, необходимо было проверить граф на ацикличность с помощью алгоритма поиска в глубину. Это было реализовано функцией [latex]cyclic[/latex], которая проходила по всему графу в поиске цикла. Если цикл был найден, то функция меняла значение переменной [latex]cycle_st[/latex]. Далее, если цикл был найден, то программа выводить -1, иначе применяется алгоритм топологической сортировки, реализованный в двух функциях:

void dfs (int v, vector <int> *graph, vector<bool> &used, vector <int> &answer)

20	void dfs (int v, vector <int> *graph, vector<bool> &used, vector <int> &answer)

void topological_sort(int n, vector <int> *graph, vector<bool> &used, vector <int> &answer)

30	void topological_sort(int n, vector <int> *graph, vector<bool> &used, vector <int> &answer)

После выполнения этих функций был получен топологически отсортированный список вершин, но в обратном порядке. Поэтому разворачиваем его с помощью функции [latex]reverse[/latex] .

Засчитанное решение на e-olymp.com.

Код решения на ideone.com.

Related Images:

e-olymp 2267. Journey

03/06/2016 by Таран Таня

The army of Rzeczpospolita is moving from the city Kostroma to the village Domnino. Two hetmans, Stefan and Konstantin, lead the army.

Stefan procured the roadmap of Kostroma province, and every night he routes the army from one village to the other along some road. Konstantin bought the map of secret trails between villages in advance, and every day he leads the march along the one of such trails. Each hetman asks their guide Ivan Susanin for a route before each march.

The length of each road is indicated on Stefan’s map. So Stefan knows the minimal distance from each village to the Domnino village according to his map. Similarly Konstantin knows the minimal distance from each village to Domnino village along trails on his map.

Ivan Susanin does not want to be disclosed as a secret agent, so each time he chooses a road (for Stefan) or a trail (for Konstantin) so, that the minimal distance to the Domnino village according to the map owned by the asking hetman is strictly decreasing.

Help Ivan to ﬁnd the longest possible route to the Domnino village.

Input

The ﬁrst line contains three integer numbers [latex]n, s[/latex] and [latex]t[/latex] — number of villages in Kostroma province, and numbers of start and Domnino village [latex](2 \le n \le 1000; 1 \le s; t \le n)[/latex]. Villages are numbered from [latex]1[/latex] to [latex]n[/latex]. Start and Domnino villages are distinct.

Two blocks follow, the ﬁrst one describing Stefan’s map, and the second one describing Konstantin’s map.

The first line of each block contains an integer number [latex]m[/latex] — the number of roads/trails between villages [latex](n-1 \le m \le 100000)[/latex]. Each of the following [latex]m[/latex]lines contains three integer numbers [latex]a, b[/latex], and [latex]l[/latex] — describing the road/trail between villages [latex]a[/latex] and [latex]b[/latex] of length [latex]l[/latex] [latex](1 \le a, b \le n; 1 \le l \le 10^6)[/latex].

Rzeczpospolita army can move in any direction along a road or a trail. It’s guaranteed that one can travel from any village to any other using each of the maps. The army starts its movement in the evening from the village number and moves one road each night and one trail each day.

Output

Output the total length of the longest route that Ivan Susanin can arrange for Rzeczpospolita army before reaching the Domnino village (along the roads and trails). If Ivan Susanin can route the army forever without reaching the Domnino village, output the number «[latex]-1[/latex]».

Tests

№	Input	Output
1	5 1 5 5 1 2 2 1 4 2 2 3 1 3 4 1 5 3 1 4 1 2 2 2 4 2 2 3 1 2 5 2	-1
2	3 1 3 4 1 2 10 2 3 10 1 3 20 2 3 30 4 2 1 10 1 3 10 1 1 10 2 3 10	20

Algorithm

The problem has been resolved together with Sploshnov Kirill.

So, we are dealing with a rather cumbersome task for the graphs, therefore we analyze it consistently. To get started we define the data structure

struct Route {
    int color;
    unsigned int to; 
    unsigned int length;
};

struct Route {

int color;

unsigned int to;

unsigned int length;

};

because dealing with the routes and subsequently, we will have to color our edges. For convenience, we don’t think about two maps as about different graphs, and can establish one graph, where edges of each map are painted in a different color.
For example edges of first map color in RED, and the other in BLUE. Then select the first map is equivalent to passing by red edges, or blue otherwise. In this way, route, that we are looking for, should be based on the successively alternating colors of the edges.
Proceed directly to the solution.
From the condition is understandable, that each hetman knows the shortest path to the final village. This data will be needed for us too, so for each map (edges of the same color) use Dijkstra’s algorithm and find the shortest path from each vertex to the target. (Function void djikstra(vector<Route>* graph, int* distancesInColoredGraph, unsigned int quantityOfAllVertices, int finishVertex, int color); ). We need absolutely standard Dijkstra’s algorithm with the only difference that the edges of the opposite color aren’t available. You can learn more about Dijkstra’s algorithm in the sources of information listed at the end of the article.
Continue analyzing the condition, we understand, that we can’t pass over the edges so, that the shortest distance to the final vertex increased. This will help us to simplify the graph, and significantly reduce the number of possible variants of passage, namely, any bidirectional edge will be either removed completely or strictly directed. Then, passing on to the edges of the same color in each map, if it doesn’t satisfy the specified condition coloring it as DELETED. (Function void simplify(vector<Route>* graph, int* distance, unsigned int quantityOfAllVertices, int color); ).
Now we can get started with the search for the longest route. There are two options: either there is the longest path, or we can walk along the edges infinitely, if it does not contradict the statement of the problem, that is, in the combined of two maps graph there is a cycle. So we organize checks on acyclic. Now we have the right to pass along the edges only alternating colors at each step. In order to find a cycle, we use vertex coloring, and will explore the graph until we try to treat already colored vertex or not conclude that it is acyclic. (Function bool cyclicDFS(vector<Route>* graph, int* passedInRedGraph, int* passedInBlueGraph, int currentVertex, int color); ). This algorithm can be obtained after detailed acquaintance with the usual cycle searching algorithm (reference to the source is located at the end of the article). If we find any loop in this graph, then our job is over and we should just output «[latex]-1[/latex]».
Otherwise, make sure that the graph is acyclic, we are looking for the longest route. As our graph has been simplified and has no cycles, and all edges are directed, then the task of finding this way becomes computationally simple. For this declaring an array of longest distance dynamically, along the way memorizing the already calculated values, sequentially find the maximum length of the route until we arrive at the finish village. (Function int maxDistDFS(vector<Route>* graph, int* maxDistancesInRedGraph, int* maxDistancesInBlueGraph, int currentVertex, int color) ). This will be the answer to the task.

Rest details of the implementation can be found in the code of the program or in the sources of information listed at the end of the article.

Code

#include <vector>
#include <iostream>
#include <algorithm>
#define DELETED -1
#define WHITE 0
#define GREY 1
#define BLACK 2
#define RED 3
#define BLUE 4
#define MAX_INT 2147483647
using namespace std;
 
//  The structure, describing the roads/trails 
struct Route {
    int color;
    unsigned int to; 
    unsigned int length;
    //  Constructor by destination, length and color of edge
    Route(unsigned int to, unsigned int length, int color) {
        this->to = to;
        this->color = color;
        this->length = length;
    }
};
 
/*  
    Function implements ordinary Dijkstra's algorithm (for all edges of the same color)
    As a result, an array of distances filled with the minimum distance to each vertex
*/
void djikstra(vector<Route>* graph, int* distancesInColoredGraph, unsigned int quantityOfAllVertices, int finishVertex, int color) {
    int vertexWithMinDist = -1;
    bool* passed = new bool[quantityOfAllVertices];
    fill(passed, passed + quantityOfAllVertices, false);
    fill(distancesInColoredGraph, distancesInColoredGraph + quantityOfAllVertices, MAX_INT);
    distancesInColoredGraph[finishVertex] = 0;
    for (unsigned int indexOfCurrentVertex = 0; vertexWithMinDist == -1 || indexOfCurrentVertex < quantityOfAllVertices && distancesInColoredGraph[vertexWithMinDist] != MAX_INT; indexOfCurrentVertex++) {
        vertexWithMinDist = -1;
        for (unsigned int indexOfVertex = 0; indexOfVertex < quantityOfAllVertices; indexOfVertex++) {
            if (!passed[indexOfVertex] && (vertexWithMinDist == -1 || distancesInColoredGraph[indexOfVertex] < distancesInColoredGraph[vertexWithMinDist])) {
                vertexWithMinDist = indexOfVertex;
            }
        }
        passed[vertexWithMinDist] = true;
        for (unsigned int adjacentVertex = 0; adjacentVertex < graph[vertexWithMinDist].size(); adjacentVertex++) {
            if (graph[vertexWithMinDist][adjacentVertex].color == color 
                && graph[vertexWithMinDist][adjacentVertex].length + distancesInColoredGraph[vertexWithMinDist] < distancesInColoredGraph[graph[vertexWithMinDist][adjacentVertex].to]) {
                distancesInColoredGraph[graph[vertexWithMinDist][adjacentVertex].to] = graph[vertexWithMinDist][adjacentVertex].length + distancesInColoredGraph[vertexWithMinDist];
            }
        }
    }
}
 
//  Function indicates the edges we don't need as deleted (because we can't pass them)
void simplify(vector<Route>* graph, int* distance, unsigned int quantityOfAllVertices, int color) {
    //  Note as DELETED routes in which the minimum distance to finish vertex increases, cause we can't walk them on the strength of problem's condition
    for (unsigned int indexOfCurrentVertex = 0; indexOfCurrentVertex < quantityOfAllVertices; indexOfCurrentVertex++) {
        for (unsigned int adjacentVertex = 0; adjacentVertex < graph[indexOfCurrentVertex].size(); adjacentVertex++) {
            if (graph[indexOfCurrentVertex][adjacentVertex].color == color 
                && distance[indexOfCurrentVertex] <= distance[graph[indexOfCurrentVertex][adjacentVertex].to]) {
                graph[indexOfCurrentVertex][adjacentVertex].color = DELETED;
            }
        }
    }
}
 
//  Function determines whether you can go in cycle by the edges of alternating colors 
bool cyclicDFS(vector<Route>* graph, int* passedInRedGraph, int* passedInBlueGraph, int currentVertex, int color) {
    bool answer = false;
    //  Note processing vertex
    if (color == RED) {
        passedInRedGraph[currentVertex] = GREY;
    } else {
        passedInBlueGraph[currentVertex] = GREY;
    }
    /*
        Implement ordinary checking on cycle, by coloring graph
        Treat until we don't determine it is acyclic or try to color vertex that is already colored
        We should take into account the fact, that each time we alternate the color of the edges
    */
    for (unsigned int adjacentVertex = 0; adjacentVertex < graph[currentVertex].size() && !answer; adjacentVertex++) {
        if (graph[currentVertex][adjacentVertex].color == color) {
            if (color == BLUE && passedInRedGraph[graph[currentVertex][adjacentVertex].to] == GREY 
                || color == RED && passedInBlueGraph[graph[currentVertex][adjacentVertex].to] == GREY) {
                answer = true;
            }
            if (color == RED && passedInBlueGraph[graph[currentVertex][adjacentVertex].to] == WHITE) {
                if (cyclicDFS(graph, passedInRedGraph, passedInBlueGraph, graph[currentVertex][adjacentVertex].to, BLUE)) {
                    answer = true;
                }
            } else if (passedInRedGraph[graph[currentVertex][adjacentVertex].to] == WHITE) {
                if (cyclicDFS(graph, passedInRedGraph, passedInBlueGraph, graph[currentVertex][adjacentVertex].to, RED)) {
                    answer = true;
                }
            }
        }
    }
    //  Note processed vertex
    if (color == RED) {
        passedInRedGraph[currentVertex] = BLACK;
    } else {
        passedInBlueGraph[currentVertex] = BLACK;
    }
    return answer;
}
 
//  Function determines whether there is a suitable cycle in the graph
bool isCyclic(vector<Route>* graph, unsigned int quantityOfAllVertices, int currentVertex) {
    int* passedInRedGraph = new int[quantityOfAllVertices];
    int* passedInBlueGraph = new int[quantityOfAllVertices];
    fill(passedInRedGraph, passedInRedGraph + quantityOfAllVertices, WHITE);
    fill(passedInBlueGraph, passedInBlueGraph + quantityOfAllVertices, WHITE);
    return cyclicDFS(graph, passedInRedGraph, passedInBlueGraph, currentVertex, RED);
}
 
//  Function determines the longest path in the graph by the edges of alternating colors, by finding and memorizing the maximum path to each of the vertices
int maxDistDFS(vector<Route>* graph, int* maxDistancesInRedGraph, int* maxDistancesInBlueGraph, int currentVertex, int color) {
    //  Return the length of the path from the current vertex, if it's found already
    if (color == RED && maxDistancesInRedGraph[currentVertex] != -1) {
        return maxDistancesInRedGraph[currentVertex];
    }
    if (color == BLUE && maxDistancesInBlueGraph[currentVertex] != -1) {
        return maxDistancesInBlueGraph[currentVertex];
    }
    int maxDistance = -1;   //  Initially, we consider the longest path by any negative number
    for (unsigned int adjacentVertex = 0; adjacentVertex < graph[currentVertex].size(); adjacentVertex++) {
        /*
            Recursively find the longest path to the finish vertex
            We should take into account the fact, that each time we alternate the color of the edges
        */
        if (graph[currentVertex][adjacentVertex].color == color) {
            int currentMaxDistance = maxDistDFS(graph, maxDistancesInRedGraph, maxDistancesInBlueGraph, graph[currentVertex][adjacentVertex].to, 
                color == RED ? BLUE : RED) + graph[currentVertex][adjacentVertex].length;
            maxDistance = max(maxDistance, currentMaxDistance);
        }
    }
    //  Remember the results received in the process of bypassing for later use
    if (color == RED) {
        maxDistancesInRedGraph[currentVertex] = maxDistance;
    } else {
        maxDistancesInBlueGraph[currentVertex] = maxDistance;
    }
    return maxDistance;
}
 
//  Function returns the longest path in the graph from the start vertex to the finish
int getMaxDist(vector<Route>* graph, unsigned int quantityOfAllVertices, int startVertex, int finishVertex) {
    int* maxDistancesInRedGraph = new int[quantityOfAllVertices];
    int* maxDistancesInBlueGraph = new int[quantityOfAllVertices];
    fill(maxDistancesInRedGraph, maxDistancesInRedGraph + quantityOfAllVertices, -1);
    fill(maxDistancesInBlueGraph, maxDistancesInBlueGraph + quantityOfAllVertices, -1);
    maxDistancesInRedGraph[finishVertex] = 0;
    maxDistancesInBlueGraph[finishVertex] = 0;
    return maxDistDFS(graph, maxDistancesInRedGraph, maxDistancesInBlueGraph, startVertex, RED);
}
 
int main() {
    ios::sync_with_stdio(false);
    unsigned int quantityOfAllVertices, quantityOfVertices, startVertex, finishVertex, from, to, length;
    cin >> quantityOfAllVertices >> startVertex >> finishVertex;
    startVertex--; finishVertex--;  //  Shift numbering
    vector<Route>* graph = new vector<Route>[quantityOfAllVertices];    // Stores graph as array of routes for each vertex
    cin >> quantityOfVertices;
    while (quantityOfVertices--) {
        cin >> from >> to >> length;
        from--; to--;   //  Shift numbering
        if (from != to) {   //  Don't read cycles
            // Initially, all roads are bidirectional, add symmetrically
            graph[from].push_back(Route(to, length, RED));
            graph[to].push_back(Route(from, length, RED));
        }
    }
    cin >> quantityOfVertices;
    while (quantityOfVertices--) {
        cin >> from >> to >> length;
        from--; to--; 
        if (from != to) {
            graph[from].push_back(Route(to, length, BLUE));
            graph[to].push_back(Route(from, length, BLUE));
        }
    }
    int* distancesInRedGraph = new int[quantityOfAllVertices];  //  Shortest distances from each vertex to the final by red edges
    int* distancesInBlueGraph = new int[quantityOfAllVertices]; //  Shortest distances from each vertex to the final by blue edges
    djikstra(graph, distancesInRedGraph, quantityOfAllVertices, finishVertex, RED);     //  Find and remember the shortest path by the red edges
    djikstra(graph, distancesInBlueGraph, quantityOfAllVertices, finishVertex, BLUE);   //  Find and remember the shortest path by the blue edges
    simplify(graph, distancesInRedGraph, quantityOfAllVertices, RED);   //  Note red edges which we can't pass, so that later they don't take into account
    simplify(graph, distancesInBlueGraph, quantityOfAllVertices, BLUE); //  Note blue edges which we can't pass, so that later they don't take into account
    cout << (isCyclic(graph, quantityOfAllVertices, startVertex) ? -1 : getMaxDist(graph, quantityOfAllVertices, startVertex, finishVertex)) << endl;
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

#include <vector>

#include <iostream>

#include <algorithm>

#define DELETED -1

#define WHITE 0

#define GREY 1

#define BLACK 2

#define RED 3

#define BLUE 4

#define MAX_INT 2147483647

using namespace std;

// The structure, describing the roads/trails

struct Route {

int color;

unsigned int to;

unsigned int length;

// Constructor by destination, length and color of edge

Route(unsigned int to, unsigned int length, int color) {

this->to = to;

this->color = color;

this->length = length;

}

};

Function implements ordinary Dijkstra's algorithm (for all edges of the same color)

As a result, an array of distances filled with the minimum distance to each vertex

void djikstra(vector<Route>* graph, int* distancesInColoredGraph, unsigned int quantityOfAllVertices, int finishVertex, int color) {

int vertexWithMinDist = -1;

bool* passed = new bool[quantityOfAllVertices];

fill(passed, passed + quantityOfAllVertices, false);

fill(distancesInColoredGraph, distancesInColoredGraph + quantityOfAllVertices, MAX_INT);

distancesInColoredGraph[finishVertex] = 0;

for (unsigned int indexOfCurrentVertex = 0; vertexWithMinDist == -1 || indexOfCurrentVertex < quantityOfAllVertices && distancesInColoredGraph[vertexWithMinDist] != MAX_INT; indexOfCurrentVertex++) {

vertexWithMinDist = -1;

for (unsigned int indexOfVertex = 0; indexOfVertex < quantityOfAllVertices; indexOfVertex++) {

if (!passed[indexOfVertex] && (vertexWithMinDist == -1 || distancesInColoredGraph[indexOfVertex] < distancesInColoredGraph[vertexWithMinDist])) {

vertexWithMinDist = indexOfVertex;

}

passed[vertexWithMinDist] = true;

for (unsigned int adjacentVertex = 0; adjacentVertex < graph[vertexWithMinDist].size(); adjacentVertex++) {

if (graph[vertexWithMinDist][adjacentVertex].color == color

&& graph[vertexWithMinDist][adjacentVertex].length + distancesInColoredGraph[vertexWithMinDist] < distancesInColoredGraph[graph[vertexWithMinDist][adjacentVertex].to]) {

distancesInColoredGraph[graph[vertexWithMinDist][adjacentVertex].to] = graph[vertexWithMinDist][adjacentVertex].length + distancesInColoredGraph[vertexWithMinDist];

}

// Function indicates the edges we don't need as deleted (because we can't pass them)

void simplify(vector<Route>* graph, int* distance, unsigned int quantityOfAllVertices, int color) {

// Note as DELETED routes in which the minimum distance to finish vertex increases, cause we can't walk them on the strength of problem's condition

for (unsigned int indexOfCurrentVertex = 0; indexOfCurrentVertex < quantityOfAllVertices; indexOfCurrentVertex++) {

for (unsigned int adjacentVertex = 0; adjacentVertex < graph[indexOfCurrentVertex].size(); adjacentVertex++) {

if (graph[indexOfCurrentVertex][adjacentVertex].color == color

&& distance[indexOfCurrentVertex] <= distance[graph[indexOfCurrentVertex][adjacentVertex].to]) {

graph[indexOfCurrentVertex][adjacentVertex].color = DELETED;

}

// Function determines whether you can go in cycle by the edges of alternating colors

bool cyclicDFS(vector<Route>* graph, int* passedInRedGraph, int* passedInBlueGraph, int currentVertex, int color) {

bool answer = false;

// Note processing vertex

if (color == RED) {

passedInRedGraph[currentVertex] = GREY;

} else {

passedInBlueGraph[currentVertex] = GREY;

}

Implement ordinary checking on cycle, by coloring graph

Treat until we don't determine it is acyclic or try to color vertex that is already colored

We should take into account the fact, that each time we alternate the color of the edges

for (unsigned int adjacentVertex = 0; adjacentVertex < graph[currentVertex].size() && !answer; adjacentVertex++) {

if (graph[currentVertex][adjacentVertex].color == color) {

if (color == BLUE && passedInRedGraph[graph[currentVertex][adjacentVertex].to] == GREY

|| color == RED && passedInBlueGraph[graph[currentVertex][adjacentVertex].to] == GREY) {

answer = true;

}

if (color == RED && passedInBlueGraph[graph[currentVertex][adjacentVertex].to] == WHITE) {

if (cyclicDFS(graph, passedInRedGraph, passedInBlueGraph, graph[currentVertex][adjacentVertex].to, BLUE)) {

answer = true;

}

} else if (passedInRedGraph[graph[currentVertex][adjacentVertex].to] == WHITE) {

if (cyclicDFS(graph, passedInRedGraph, passedInBlueGraph, graph[currentVertex][adjacentVertex].to, RED)) {

answer = true;

}

// Note processed vertex

if (color == RED) {

passedInRedGraph[currentVertex] = BLACK;

} else {

passedInBlueGraph[currentVertex] = BLACK;

}

return answer;

}

// Function determines whether there is a suitable cycle in the graph

bool isCyclic(vector<Route>* graph, unsigned int quantityOfAllVertices, int currentVertex) {

int* passedInRedGraph = new int[quantityOfAllVertices];

int* passedInBlueGraph = new int[quantityOfAllVertices];

fill(passedInRedGraph, passedInRedGraph + quantityOfAllVertices, WHITE);

fill(passedInBlueGraph, passedInBlueGraph + quantityOfAllVertices, WHITE);

return cyclicDFS(graph, passedInRedGraph, passedInBlueGraph, currentVertex, RED);

}

// Function determines the longest path in the graph by the edges of alternating colors, by finding and memorizing the maximum path to each of the vertices

int maxDistDFS(vector<Route>* graph, int* maxDistancesInRedGraph, int* maxDistancesInBlueGraph, int currentVertex, int color) {

// Return the length of the path from the current vertex, if it's found already

if (color == RED && maxDistancesInRedGraph[currentVertex] != -1) {

return maxDistancesInRedGraph[currentVertex];

}

if (color == BLUE && maxDistancesInBlueGraph[currentVertex] != -1) {

return maxDistancesInBlueGraph[currentVertex];

}

int maxDistance = -1; // Initially, we consider the longest path by any negative number

for (unsigned int adjacentVertex = 0; adjacentVertex < graph[currentVertex].size(); adjacentVertex++) {

Recursively find the longest path to the finish vertex

We should take into account the fact, that each time we alternate the color of the edges

if (graph[currentVertex][adjacentVertex].color == color) {

int currentMaxDistance = maxDistDFS(graph, maxDistancesInRedGraph, maxDistancesInBlueGraph, graph[currentVertex][adjacentVertex].to,

color == RED ? BLUE : RED) + graph[currentVertex][adjacentVertex].length;

maxDistance = max(maxDistance, currentMaxDistance);

}

// Remember the results received in the process of bypassing for later use

if (color == RED) {

maxDistancesInRedGraph[currentVertex] = maxDistance;

} else {

maxDistancesInBlueGraph[currentVertex] = maxDistance;

}

return maxDistance;

}

// Function returns the longest path in the graph from the start vertex to the finish

int getMaxDist(vector<Route>* graph, unsigned int quantityOfAllVertices, int startVertex, int finishVertex) {

int* maxDistancesInRedGraph = new int[quantityOfAllVertices];

int* maxDistancesInBlueGraph = new int[quantityOfAllVertices];

fill(maxDistancesInRedGraph, maxDistancesInRedGraph + quantityOfAllVertices, -1);

fill(maxDistancesInBlueGraph, maxDistancesInBlueGraph + quantityOfAllVertices, -1);

maxDistancesInRedGraph[finishVertex] = 0;

maxDistancesInBlueGraph[finishVertex] = 0;

return maxDistDFS(graph, maxDistancesInRedGraph, maxDistancesInBlueGraph, startVertex, RED);

}

int main() {

ios::sync_with_stdio(false);

unsigned int quantityOfAllVertices, quantityOfVertices, startVertex, finishVertex, from, to, length;

cin >> quantityOfAllVertices >> startVertex >> finishVertex;

startVertex--; finishVertex--; // Shift numbering

vector<Route>* graph = new vector<Route>[quantityOfAllVertices]; // Stores graph as array of routes for each vertex

cin >> quantityOfVertices;

while (quantityOfVertices--) {

cin >> from >> to >> length;

from--; to--; // Shift numbering

if (from != to) { // Don't read cycles

// Initially, all roads are bidirectional, add symmetrically

graph[from].push_back(Route(to, length, RED));

graph[to].push_back(Route(from, length, RED));

}

cin >> quantityOfVertices;

while (quantityOfVertices--) {

cin >> from >> to >> length;

from--; to--;

if (from != to) {

graph[from].push_back(Route(to, length, BLUE));

graph[to].push_back(Route(from, length, BLUE));

}

int* distancesInRedGraph = new int[quantityOfAllVertices]; // Shortest distances from each vertex to the final by red edges

int* distancesInBlueGraph = new int[quantityOfAllVertices]; // Shortest distances from each vertex to the final by blue edges

djikstra(graph, distancesInRedGraph, quantityOfAllVertices, finishVertex, RED); // Find and remember the shortest path by the red edges

djikstra(graph, distancesInBlueGraph, quantityOfAllVertices, finishVertex, BLUE); // Find and remember the shortest path by the blue edges

simplify(graph, distancesInRedGraph, quantityOfAllVertices, RED); // Note red edges which we can't pass, so that later they don't take into account

simplify(graph, distancesInBlueGraph, quantityOfAllVertices, BLUE); // Note blue edges which we can't pass, so that later they don't take into account

cout << (isCyclic(graph, quantityOfAllVertices, startVertex) ? -1 : getMaxDist(graph, quantityOfAllVertices, startVertex, finishVertex)) << endl;

return 0;

}

Related Images:

e-olymp 2401. Обход в ширину

31/05/2016 by Андрей Яроцкий

Задача 2401

Условие

Дан неориентированный граф. В нём необходимо найти расстояние от одной заданной вершины до другой.

Входные данные

В первой строке содержится три натуральных числа [latex]n, s[/latex] и [latex]f (1 [/latex] [latex]\le[/latex] [latex]s, f[/latex] [latex]\le[/latex] [latex]n[/latex] [latex]\le[/latex] [latex]100)[/latex] — количество вершин в графе и номера начальной и конечной вершин соответственно. Далее в n строках задана матрица смежности графа. Если значение в [latex]j[/latex]-м элементе [latex]i[/latex]-й строки равно [latex]1[/latex], то в графе есть направленное ребро из вершины [latex]i[/latex] в вершину [latex]j[/latex].

Выходные данные

Вывести минимальное расстояние от начальной вершины до конечной. Если пути не существует, выведите [latex]0[/latex].

Тесты

№	Входные данные	Выходные данные
1	1 1 1 1	0
2	3 1 3 0 1 0 1 0 0 0 0 0	0
3	4 4 3 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0	2
4	5 1 4 0 1 0 0 1 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 1 0 0 1 0	2

#include <iostream>
using namespace std;

struct node{
    int value;
    node * next;
    node(int v, node * n = NULL){
        value = v;
        next = n;
    }
};
 
struct queue{ // Структура очередь
    node * start;
    node * finish;
    int len = 0;
    queue(node * s = NULL, node * f = NULL){
        start = s;
        finish = f;
    }
    string push(int n){
        if(len == 0){
            node * new_node = new node(n,finish);
            start = new_node;
            finish = new_node;
        }else{
            node * new_node = new node(n,NULL);
            start -> next = new_node;
            start = new_node;
        }
        len++;
        return "ok";
    }
    int pop(){
        int v = finish -> value;
        finish = finish -> next;
        len--;
        return v;
    }
    int front(){
        return finish -> value;
    }
    int size(){
        return len;
    }
};

int main() {
    int n, s, f;
    cin >> n >> s >> f;
    int graph[n][n];
    int dist[n]; // Массив расстояний от начальной до i-ой вершины
    bool used[n];
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cin >> graph[i][j];
        }
    }
    for(int i = 0; i < n; i++){
        dist[i] = 0;
        used[i] = false;
    }
    queue vertex; // Очередь вершин
    vertex.push(s-1);
    used[s-1] = true;
    while(vertex.size() != 0){
        int v = vertex.front();
        for(int i = 0; i < n; i++){
            if(graph[v][i] == 1 && used[i] == false){
                vertex.push(i);
                dist[i] = dist[v] + 1; 
                used[i] = true; // i-ая вершина пройдена и не будет корректироваться позже
            }
        }
        used[v] = true;
        vertex.pop();
    }
    cout << dist[f-1];
    return 0;
}

#include <iostream>

using namespace std;

struct node{

int value;

node * next;

node(int v, node * n = NULL){

value = v;

next = n;

}

};

struct queue{ // Структура очередь

node * start;

node * finish;

int len = 0;

queue(node * s = NULL, node * f = NULL){

start = s;

finish = f;

}

string push(int n){

if(len == 0){

node * new_node = new node(n,finish);

start = new_node;

finish = new_node;

}else{

node * new_node = new node(n,NULL);

start -> next = new_node;

start = new_node;

}

len++;

return "ok";

}

int pop(){

int v = finish -> value;

finish = finish -> next;

len--;

return v;

}

int front(){

return finish -> value;

}

int size(){

return len;

}

};

int main() {

int n, s, f;

cin >> n >> s >> f;

int graph[n][n];

int dist[n]; // Массив расстояний от начальной до i-ой вершины

bool used[n];

for(int i = 0; i < n; i++){

for(int j = 0; j < n; j++){

cin >> graph[i][j];

}

for(int i = 0; i < n; i++){

dist[i] = 0;

used[i] = false;

}

queue vertex; // Очередь вершин

vertex.push(s-1);

used[s-1] = true;

while(vertex.size() != 0){

int v = vertex.front();

for(int i = 0; i < n; i++){

if(graph[v][i] == 1 && used[i] == false){

vertex.push(i);

dist[i] = dist[v] + 1;

used[i] = true; // i-ая вершина пройдена и не будет корректироваться позже

}

used[v] = true;

vertex.pop();

}

cout << dist[f-1];

return 0;

}

Решение

Для решения данной задачи необходимо использовать алгоритм «Поиск в ширину». Суть данного алгоритма полагает в том, что все вершины, начиная с начальной, помещаются в структуру очередь [latex](queue)[/latex] в порядке удаления от начальной вершины. По мере заполнения очереди, каждой вершине приписывается величина расстояния [latex](dist)[/latex] от начальной вершины, после чего соответствующая вершина помечается как пройденная [latex](used)[/latex] и её расстояние от начальной вершины более не переписывается даже при повторном просмотре. Таким образом, каждой вершине, для которой существует путь, соединяющий её с начальной вершиной, сопоставляется минимальное расстояние от нее до начальной вершины. Если такого пути не существует, расстояние остается равным нулю. Подробней об этом алгоритме можно прочесть здесь

Ссылки

Код программы на ideone.com

Условие задачи

Решенная задача

Related Images:

e-olymp 974. Флойд-1

27/05/2016 by Радик Сиденко

Полный ориентированный взвешенный граф задан матрицей смежности. Постройте матрицу кратчайших путей между его вершинами. Гарантируется, что в графе нет циклов отрицательного веса.

Входные данные

В первой строке записано количество вершин графа n (1 ≤ n ≤ 100). В следующих n строках записано по n чисел — матрица смежности графа (j-ое число в i-ой строке соответствует весу ребра из вершины i в вершину j). Все числа по модулю не превышают 100. На главной диагонали матрицы — всегда нули.

Выходные данные

Выведите n строк по n чисел — матрицу кратчайших расстояний между парами вершин. j-ое число в i-ой строке должно равняться весу кратчайшего пути из вершины i в вершину j.

Сам алгоритм хорошо описан на wikipedia

А вот сам код

#include <iostream>
using namespace std;

    
int main(){
    int n;
    cin >> n;
    int w[n][n];
    for( int i=0 ; i<n ; i++ ){
        for( int j=0 ; j<n ; j++ ){
            cin >> w[i][j];
        }
    }
    
    for( int k=0 ; k<n ; k++ ){
        for( int i=0 ; i<n ; i++ ){
            for( int j=0 ; j<n ; j++ ){
                w[i][j] = min(w[i][j], w[i][k]+w[k][j]);
            }
        }
    }
    
    for( int i=0 ; i<n ; i++ ){
        for( int j=0 ; j<n ; j++ ){
            cout << w[i][j] << " ";
        }
        cout<<endl;
    }
}

#include <iostream>

using namespace std;

int main(){

int n;

cin >> n;

int w[n][n];

for( int i=0 ; i<n ; i++ ){

for( int j=0 ; j<n ; j++ ){

cin >> w[i][j];

}

for( int k=0 ; k<n ; k++ ){

for( int i=0 ; i<n ; i++ ){

for( int j=0 ; j<n ; j++ ){

w[i][j] = min(w[i][j], w[i][k]+w[k][j]);

}

for( int i=0 ; i<n ; i++ ){

for( int j=0 ; j<n ; j++ ){

cout << w[i][j] << " ";

}

cout<<endl;

}

Условие на e-olymp.com
Решение на e-olymp.com
Код на ideone.com

Related Images:

e-olymp 982. Связность

15/05/2016 by Женя Максимова

Задача. Проверить, является ли заданный неориентированный граф связным, то есть что из любой вершины можно по рёбрам этого графа попасть в любую другую.

Входные данные

В первой строке заданы количество вершин [latex]n[/latex] и ребер [latex]m[/latex] в графе соответственно [latex](1 \leq n \leq 100, 1 \leq m \leq 10000)[/latex]. Каждая из следующих m строк содержит по два числа [latex]u_i[/latex] и [latex]v_i[/latex] [latex](1 \leq u_i, v_i \leq n);[/latex] каждая такая строка означает, что в графе существует ребро между вершинами [latex]u_i[/latex] и [latex]v_i[/latex].

Выходные данные

Выведите «YES», если граф является связным и «NO» в противном случае.

Тесты

Тесты, взятые с e-olymp.com

Test	Input	Output
1	3 2 1 2 3 2	YES
2	3 1 1 3	NO

Мои тесты

Test	Input	Output
1	4 2 1 2 3 4	NO
2	4 5 1 2 2 1 2 4 2 4 4 2	NO
3	5 4 1 2 5 1 3 5 4 3	YES

Код программы

#include <bits/stdc++.h>
using namespace std;

#define in_range(x,y,z) for(int x=y; x<z; x++)

int main()
{
  int m,n;
  cin >> n >> m;
  vector < vector<int> > g(n); // граф
  int s=0; // начальная вершина
  in_range(i,0,m) // считывание графа
    {
      int u,v;
      cin >> u >> v;
      g[u-1].push_back(v-1);
      g[v-1].push_back(u-1);
    }
  queue<int> q; // очередь с вершинами, которые мы рассматриваем на данном этапе
  q.push (s);
  vector<bool> used (n); // логический массив, указывающий, посещена ли вершина
  used[s] = true;
  while (!q.empty()) // пока мы не обойдем все вершины, которые можно достигнуть из данной
    {
      int v = q.front();
      q.pop(); // достаем из головы очереди одну вершину
      for (size_t i=0; i<g[v].size(); ++i) //просмотрим все ребра, исходящие из данной вершины
        {
          int to = g[v][i];
          if (!used[to]) // если текущая вершина еще не была посещена
            {
              used[to] = true; //отмечаем, что мы ее посетили
              q.push (to); // помещаем в очередь
            }
        }
    }
  vector<bool>::iterator it;
  it = find (used.begin(), used.end(), false); // проверяем, остались ли еще непосещенные вершины
  if (it == used.end())
    cout << "YES"; // если все вершины посещены, то граф связный
  else
    cout << "NO";
  return 0;
}

#include <bits/stdc++.h>

using namespace std;

#define in_range(x,y,z) for(int x=y; x<z; x++)

int main()

{

int m,n;

cin >> n >> m;

vector < vector<int> > g(n); // граф

int s=0; // начальная вершина

in_range(i,0,m) // считывание графа

{

int u,v;

cin >> u >> v;

g[u-1].push_back(v-1);

g[v-1].push_back(u-1);

}

queue<int> q; // очередь с вершинами, которые мы рассматриваем на данном этапе

q.push (s);

vector<bool> used (n); // логический массив, указывающий, посещена ли вершина

used[s] = true;

while (!q.empty()) // пока мы не обойдем все вершины, которые можно достигнуть из данной

{

int v = q.front();

q.pop(); // достаем из головы очереди одну вершину

for (size_t i=0; i<g[v].size(); ++i) //просмотрим все ребра, исходящие из данной вершины

{

int to = g[v][i];

if (!used[to]) // если текущая вершина еще не была посещена

{

used[to] = true; //отмечаем, что мы ее посетили

q.push (to); // помещаем в очередь

}

vector<bool>::iterator it;

it = find (used.begin(), used.end(), false); // проверяем, остались ли еще непосещенные вершины

if (it == used.end())

cout << "YES"; // если все вершины посещены, то граф связный

else

cout << "NO";

return 0;

}

Алгоритм

Чтобы установить, является ли граф связным, я использовала удобный для этого алгоритм поиска в ширину. Он заключается в следующем: начиная с какой-то вершины, мы поочередно просматриваем все вершины, соседние с ней. Каждую посещенную вершину мы помечаем маркером. Затем повторяем этот процесс для каждой из соседних вершин, и так далее. Поиск будет продолжаться, пока мы не обойдем все вершины, которые можно достигнуть из данной. Если после этого в графе осталась хотя бы одна не помеченная вершина, значит из нее нельзя попасть в помеченные, то есть граф не является связным. При этом неважно, с какой вершины мы будем начинать поиск, ведь нам нужно установить сам факт, связный граф или нет.

Код программы

Засчитанное решение на сайте e-olymp.com

Related Images:

e-olymp 1455. Цикл

12/05/2016 by Катя Писова

Задача

Дан граф. Определить, есть ли в нем цикл отрицательного веса, и если да, то вывести его.

Входные данные

Первая строка содержит количество вершин графа n (1 ≤ n ≤ 100). В следующих n строках находится по n чисел — матрица смежности графа. Веса ребер не превышают по модулю 10000. Если ребра нет, соответствующее значение равно 100000.

Выходные данные

В первой строке выведите «YES«, если цикл существует, или «NO» в противном случае. При наличии цикла выведите во второй строке количество вершин в нем (считая одинаковыми первую и последнюю) и в третьей строке — вершины, входящие в этот цикл в порядке обхода. Если циклов несколько — выведите любой.

Тесты

Входные данные	Выходные данные:
2 0 -1 -1 0	YES 3 1 2 1
4 0 2 0 9 2 0 6 0 0 6 0 -3 9 0 -3 0	YES 3 3 4 3
3 0 2 3 2 0 1 3 1 0	NO

Код программы

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct edge{
    int from, to, cost;
};
const int INF = 1e9;;

int main(){
    int n;
    cin >> n;
    vector <edge> E;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            int x;
            cin >> x;
            if(x != 0 && x != 100000){
                E.push_back({i,j,x});
            }
        }
    }
    int x ;
    vector<int> d(n, INF), p(n, -1);
    d[0] = 0;
    for(int i = 0; i < n; i++){
        x = -1;
        for(int j = 0; j < E.size(); j++){
            int from = E[j].from;
            int to = E[j].to;
            int cost = E[j].cost;
            if(d[to] > d[from] + cost ){
                d[to] = max(d[from] + cost, -INF);
                p[to] = from;
                x = to;
            }
        }
    }
    if(x == -1){
        cout << "NO" << endl;
    }else{
        int y = x;
        for(int i = 0; i < n; i++){
            y = p[y];
        }
        vector <int> path;
        for(int cur = y;; cur = p[cur]){
            path.push_back(cur);
            if(cur == y && path.size() > 1){
                break;
            }
        }
        reverse(path.begin(), path.end());
        cout << "YES" << endl;
        cout << path.size() << endl;
        for(int i = 0; i < path.size(); i++){
            cout << path[i] + 1;
            if(i != path.size()-1){
                cout << ' ';
            }
        }
        cout << endl;
    }
    return 0;
}

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

struct edge{

int from, to, cost;

};

const int INF = 1e9;;

int main(){

int n;

cin >> n;

vector <edge> E;

for(int i = 0; i < n; i++){

for(int j = 0; j < n; j++){

int x;

cin >> x;

if(x != 0 && x != 100000){

E.push_back({i,j,x});

}

int x ;

vector<int> d(n, INF), p(n, -1);

d[0] = 0;

for(int i = 0; i < n; i++){

x = -1;

for(int j = 0; j < E.size(); j++){

int from = E[j].from;

int to = E[j].to;

int cost = E[j].cost;

if(d[to] > d[from] + cost ){

d[to] = max(d[from] + cost, -INF);

p[to] = from;

x = to;

}

if(x == -1){

cout << "NO" << endl;

}else{

int y = x;

for(int i = 0; i < n; i++){

y = p[y];

}

vector <int> path;

for(int cur = y;; cur = p[cur]){

path.push_back(cur);

if(cur == y && path.size() > 1){

break;

}

reverse(path.begin(), path.end());

cout << "YES" << endl;

cout << path.size() << endl;

for(int i = 0; i < path.size(); i++){

cout << path[i] + 1;

if(i != path.size()-1){

cout << ' ';

}

cout << endl;

}

return 0;

}

Алгоритм решения:

Для решения данной задачи задействован алгоритм Беллмана-Форда, который позволяет проверить наличие или отсутствие цикла отрицательного веса в графе, а при его наличии — найти один из таких циклов. Создадим вектор, который будет содержать в себе элементы матрицы смежности графа. По определению смежных вершин графа, учитывая условие задачи (если ребра нет, соответствующее значение равно [latex]100000[/latex]), заполним этот вектор. Далее будем использовать алгоритм Беллмана-Форда. Если алгоритм даст отрицательный ответ на вопрос задачи, то выводим NO. Если цикл все-таки существует, то выводим YES. В вектор записываем вершины, входящие в цикл отрицательного веса. Далее выводим их количество, а затем и сами вершины в порядке обхода.

Для получения подробной информации об алгоритме Беллмана-Форда можно перейти по данной ссылке
Ссылка на засчитанное решение на e-olymp
Ссылка на условие задачи
Ссылка на решение задачи на ideone.com

Related Images:

e-olimp 5079. Транзитивность ориентированного графа

11/05/2016 by Таня Корнилова

Задача e-olimp 5079.

Условие

Напомним, что ориентированный граф называется транзитивным, если для любых трех различных вершин [latex]u[/latex], [latex]v[/latex] и [latex]w[/latex] из того, что из [latex]u[/latex] в вершину [latex]v[/latex] ведет ребро и из вершины [latex]v[/latex] в вершину [latex]w[/latex] ведет ребро, следует, что из вершины [latex]u[/latex] в вершину [latex]w[/latex] ведет ребро.

Проверьте, что заданный ориентированный граф является транизитивным.

Входные данные

Входной файл содержит число [latex]n (1 \le n \le100)[/latex] — число вершин в графе, и затем [latex]n[/latex] строк по [latex]n[/latex] чисел, каждое из которых равно 0 или 1 — его матрицу смежности.

Выходные данные

Выведите в выходной файл YES если граф является транзитивным и NO в противном случае.

Тесты

Входные данные	Выходные данные
3 0 1 1 0 0 1 0 0 0	YES
3 0 1 1 1 0 0 0 1 0	NO

Код программы

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    bool arr[n][n];
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            cin >> arr[i][j];
        }
    }
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            // если существует ориентированное ребро, соединяющее вершины i и j
            if(arr[i][j]) { 
                for(int z = 0; z < n; z++) {
                    // если из вершины j в вершину z ведёт ребро, но из i в z - нет, то граф нетранзитивен
                    if(arr[j][z] && !arr[i][z]) { 
                        cout << "NO";
                        return 0;
                    }   
                }   
            }
        }
    }
    cout << "YES";
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

bool arr[n][n];

for(int i = 0; i < n; i++) {

for(int j = 0; j < n; j++) {

cin >> arr[i][j];

}

for(int i = 0; i < n; i++) {

for(int j = 0; j < n; j++) {

// если существует ориентированное ребро, соединяющее вершины i и j

if(arr[i][j]) {

for(int z = 0; z < n; z++) {

// если из вершины j в вершину z ведёт ребро, но из i в z - нет, то граф нетранзитивен

if(arr[j][z] && !arr[i][z]) {

cout << "NO";

return 0;

}

cout << "YES";

return 0;

}

Ссылка на засчитанное решение.
Для запроса на выполнение нажать здесь.

Решение

Представим матрицу смежности графа в виде двумерного массива. Тогда, если [latex]a[i][j] = 1[/latex], то из вершины [latex]i[/latex] в вершину [latex]j[/latex] ведёт ребро. Проверяем с помощью циклов транзитивность графа, то есть если из вершины [latex]i[/latex] в вершину [latex]j[/latex] ведёт ребро и из вершины [latex]j[/latex] в вершину [latex]z[/latex], то граф транзитивен, если есть ребро [latex]a[i][z][/latex].

Related Images:

e-olymp 1453. Форд-Беллман

30/04/2016 by Молоканов Юрий

Условие

Дан ориентированный граф, в котором могут быть кратные ребра и петли. Каждое ребро имеет вес, выражающийся целым числом (возможно, отрицательным). Гарантируется, что циклы отрицательного веса отсутствуют. Требуется посчитать длины кратчайших путей от вершины номер [latex]1[/latex] до всех остальных вершин.

Сначала записано количество вершин графа [latex]n[/latex] ([latex]1 \leq n \leq 100[/latex]), за которым идет количество ребер [latex]m[/latex] ([latex]1 \leq m \leq 10000[/latex]) Следующие [latex]m[/latex] троек чисел описывают ребра: начало ребра, конец ребра и его вес (вес — целое число от [latex]-100[/latex] до [latex]100[/latex]).

Выведите [latex]n[/latex] чисел — расстояния от вершины номер [latex]1[/latex] до всех вершин графа. Если пути до соответствующей вершины не существует, вместо длины пути выведите число [latex]30000[/latex].

Тестирование

№	Входные данные	Выходные данные
1	4 5 1 2 10 2 3 10 1 3 100 3 1 -10 2 3 1	0 10 11 30000

Код

#include <vector>
#include <cmath>
using namespace std;

struct edge {
	int a, b, cost;
	edge(int na, int nb, int nc) {
		int a = na;
		int b = nb;
		int cost = nc;
	}
};

const int INF = 30000;
 
int main() {
	int n, m, a, b, c;
	vector<edge> e;
	cin >> n >> m;
	for(int i = 0; i < m; i++) {
		cin >> a >> b >> c;
		edge newEdge(a, b, c);
		e.push_back(newEdge);
	}
	vector<int> d(n, INF);
	d[0] = 0;
	for(int i = 0; i < n - 1; i++)
		for(int j = 0; j < m; j++)
			if(d[e[j].a] < INF)
				d[e[j].b] = min(d[e[j].b], d[e[j].a] + e[j].cost);
	for(int i = 0; i < n - 1; i++)
		cout << d[i] << ' ';
	return 0;
}

#include <vector>

#include <cmath>

using namespace std;

struct edge {

int a, b, cost;

edge(int na, int nb, int nc) {

int a = na;

int b = nb;

int cost = nc;

}

};

const int INF = 30000;

int main() {

int n, m, a, b, c;

vector<edge> e;

cin >> n >> m;

for(int i = 0; i < m; i++) {

cin >> a >> b >> c;

edge newEdge(a, b, c);

e.push_back(newEdge);

}

vector<int> d(n, INF);

d[0] = 0;

for(int i = 0; i < n - 1; i++)

for(int j = 0; j < m; j++)

if(d[e[j].a] < INF)

d[e[j].b] = min(d[e[j].b], d[e[j].a] + e[j].cost);

for(int i = 0; i < n - 1; i++)

cout << d[i] << ' ';

return 0;

}

Решение

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

В основе программы лежит алгоритм, идея которого заключается не в переборе подстрок с последующим поиском граней в них (так как это было бы очень ресурсозатратно), а в переборе смещений префикса и суффикса друг относительно друга и вычислении максимальной грани, которую можно получить в каждом из таких смещений. Цикл перебора выглядит следующим образом:

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

for(int i = 1; i < s.length() && s.length() - i > max; i++) {	
	int j = 0;
/*
Перебираем различные длины префиксов (суффиксов), пока не дойдем до длины 1 и пока можем встретить грань, длиннее хранящейся.
i - первый символ очередного суффикса
j - длина текущей грани и первый символ очередного префикса
*/

for(int i = 1; i < s.length() && s.length() - i > max; i++) {

int j = 0;

Перебираем различные длины префиксов (суффиксов), пока не дойдем до длины 1 и пока можем встретить грань, длиннее хранящейся.

i - первый символ очередного суффикса

j - длина текущей грани и первый символ очередного префикса

Начнем параллельно «двигаться» вправо по строке, проверяя на совпадение соответствующие символы префикса и суффикса и продолжая до тех пор, пока не наткнемся на различные символы или пока не дойдем до конца строки. При этом будем попутно накапливать значение длины текущей грани, пока пары символов совпадают. К примеру, если в очередной итерации первые символы префикса и суффикса — это первый и третий символы строки соответственно, то сначала проверим на совпадение символы на позициях 1 и 3, затем 2 и 4, 3 и 5 и т. д.

C++

while(j < s.length() - i && s.at(j) == s.at(i + j)) j++;

1
2

while(j < s.length() - i && s.at(j) == s.at(i + j))
j++;

В виду того, что нумерация символов в строке начинается с нуля, переменная j выполняет здесь одновременно роль первого символа префикса и длины текущей грани.
Сравним длину текущей грани с длиной максимальной грани и, если необходимо, обновим значение максимальной.

Отметим, что значение переменной j, получаемое в каждой итерации, представляет собой максимально возможную длину грани либо исходной строки (если проверки на совпадение пар символов закончились из-за достижения конца строки), либо подстроки, получаемой путем отбрасывания правой части исходной до того символа, на котором обнаружилось несовпадение.

Ссылки

Условие задачи на E-Olymp;

Код программы на Ideone.com;

Подтверждение решения на E-Olymp.

Related Images:

e-olymp 5071. Проверка на неориенитрованность

29/04/2016 by Кудымовская Вика

Задача. Проверка на неориенитрованность

Условие задачи

По заданной квадратной матрице [latex]n\times n[/latex] из нулей и единиц определите, может ли данная матрица быть матрицей смежности простого неориентированного графа.

Входные данные

Входной файл содержит число [latex]n(1\leq n\leq 100)[/latex] — размер матрицы, и затем [latex]n[/latex] строк по [latex]n[/latex] чисел, каждое из которых равно [latex]0[/latex] или [latex]1[/latex] — саму матрицу.

Выходные данные

Выведите в выходной файл YES если приведенная матрица может быть матрицей смежности простого неориентированного графа и NO в противном случае.

Также условие задачи можно посмотреть здесь.

Тестирование

№	Входные данные	Выходные данные
1.	3 0 1 1 1 0 1 1 1 0	YES
2.	3 0 1 0 1 0 1 1 1 0	NO
3.	3 0 1 0 1 1 1 0 1 0	NO

Реализация

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    int n; 
    cin >> n;
    vector<int> G(n*n);
    for (int i = 0; i < G.size(); i++) 
    { 
        cin >> G[i];
    }
    int j = 0, c = 0, s = 0;
    /*с - счетчик циклов, сигнализирует о завершении текущего цикла сравнения 
    элементов i строки и j столбца; j - служит индексом для элементов столбца;
    s - счетчик столбцов, служит для задания нового начального значения индексу 
    j при переходе к следующему циклу сравнения элементов i строки и j столбца;*/
    bool f = true;              
    for (int i = 0; i < n*n; i++)//задаем цикл по всему массиву
    {
        if (G[i] != G[j]) { f=false; break; }
        if (c == n - 1)             
        {                   
            c = 0; s++; j = s;      
        }
        /*если уже сравнили n-1 строку и столбец, обнуляем c, увеличиваем s 
        и присваиваем его как новое начальное значение для индекса элементов столбца j*/
        else
        {
            j = j + n;//на каждом шаге устанавливаем индекс для элемента столбца
            c++;                
        }
    }
    for (int i = 0; i < n*n; i = i + n + 1)
    /*цикл для определения равенства нулю элементов главной диагонали - индекс 
    увеличивается на n+1 на каждом шаге*/
    {                   
        if (G[i] != 0) { f = false; break; }    
    }
    if (f) cout << "YES";
    else cout << "NO";
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main()

{

int n;

cin >> n;

vector<int> G(n*n);

for (int i = 0; i < G.size(); i++)

{

cin >> G[i];

}

int j = 0, c = 0, s = 0;

/*с - счетчик циклов, сигнализирует о завершении текущего цикла сравнения

элементов i строки и j столбца; j - служит индексом для элементов столбца;

s - счетчик столбцов, служит для задания нового начального значения индексу

j при переходе к следующему циклу сравнения элементов i строки и j столбца;*/

bool f = true;

for (int i = 0; i < n*n; i++)//задаем цикл по всему массиву

{

if (G[i] != G[j]) { f=false; break; }

if (c == n - 1)

{

c = 0; s++; j = s;

}

/*если уже сравнили n-1 строку и столбец, обнуляем c, увеличиваем s

и присваиваем его как новое начальное значение для индекса элементов столбца j*/

else

{

j = j + n;//на каждом шаге устанавливаем индекс для элемента столбца

c++;

}

for (int i = 0; i < n*n; i = i + n + 1)

/*цикл для определения равенства нулю элементов главной диагонали - индекс

увеличивается на n+1 на каждом шаге*/

{

if (G[i] != 0) { f = false; break; }

}

if (f) cout << "YES";

else cout << "NO";

return 0;

}

Алгоритм решения

Чтобы введённая матрица была матрицей смежности простого неориентированного графа, она должна, во-первых, быть симметричной, то есть элементы на соответствующих позициях должны быть равны между собой: [latex]a[i][j]=a[j][i][/latex]. Во-вторых, необходимо, чтобы элементы главной диагонали матрицы равнялись нулю. Таким образом, нам нужно проверить, выполняются ли указанные условия.
Создаём переменную f типа bool. Изначально f=true. Если при проверке на симметричность и равенство нулю главной диагонали хоть одно значение элемента матрицы не удовлетворяет условию, флаг устанавливается в «ложь» и происходит выход из цикла проверки. Это означает соответственно, что введённая матрица не является матрицей смежности неориентированного графа, — на экран выводится «NO». Если же оба условия выполняются, приведённая матрица — матрица смежности. Выводим «YES».

Подробнее о графах и матрице смежности можно прочесть, используя следующие интернет-ресурсы:

Для запроса на выполнение следует перейти по ссылке.

Ссылка на засчитанное решение на e-olymp.com.

Related Images:

e-olymp 978. Получи дерево

26/04/2016 by Павел Загинайло

Задача с сайта e-olymp.com.

Условие

Дан связный неориентированный граф без петель и кратных ребер. Разрешается удалять из него ребра. Требуется получить дерево.

Входные данные

Первая строка содержит количество вершин [latex]n[/latex] (1 ≤ [latex]n[/latex] ≤ 100) и количество ребер [latex]m[/latex] графа. Следующие [latex]m[/latex] пар чисел задают ребра графа. Гарантируется, что граф связный.

Выходные данные

Выведите [latex]n — 1[/latex] пару чисел — ребра, которые войдут в дерево. Ребра можно выводить в любом порядке.

Код

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;


/*
Объявляем структуру Ребро, которой будем пользоваться для построения графа и дерева
*/
struct edge{
    int x, y; //вершины
    edge(){}
    edge(int a, int b){
        x = a;
        y = b;
    }
};

int main() {
    int n, m;
    cin >> n >> m;
    
    vector <edge> graph (m); //ребра исходного графа
    vector <edge> tree; //ребра дерева
    vector <int> variety (n); //множество вершин
    
    /*
    variety[n] = m - вершина n принадлежит множеству m.
    Следующий цикл определяет для каждой вершины свое множество
    */
    for (int i = 0; i < n; i++){
        variety[i] = i;
    }
    
    /*
    Заполняем ребра исходного графа значениями из стандартного ввода
    */
    for (int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        graph[i].x = a;
        graph[i].y = b;
    }
    
    /*
    Проверяем вершины каждого ребра. 
    Если вершины не принадлежат одному и тому же множеству, 
    но такое ребро добавляем в наше дерево, а вершины помещаем в одно множество
    */
    for (int i = 0; i < m; i++){
        int a = graph[i].x;
        int b = graph[i].y;
        if (variety[a] != variety[b]){
            tree.push_back(graph[i]);
            int old_variety = variety[b], new_variety = variety[a];
            for (int j = 0; j < n; j++){
                if (variety[j] == old_variety){
                    variety[j] = new_variety;
                }
            }
            
            
            
        }
    }

    
    for(int i = 0; i < n - 1; i++){ //по принципу построения дерева, оно содержит n-1 ребро
        cout << tree[i].x << " " << tree[i].y;
        if (i != n-2){
            cout << endl;
        }
    }
    return 0;
}

#include <algorithm>

#include <iostream>

#include <vector>

using namespace std;

Объявляем структуру Ребро, которой будем пользоваться для построения графа и дерева

struct edge{

int x, y; //вершины

edge(){}

edge(int a, int b){

x = a;

y = b;

}

};

int main() {

int n, m;

cin >> n >> m;

vector <edge> graph (m); //ребра исходного графа

vector <edge> tree; //ребра дерева

vector <int> variety (n); //множество вершин

variety[n] = m - вершина n принадлежит множеству m.

Следующий цикл определяет для каждой вершины свое множество

for (int i = 0; i < n; i++){

variety[i] = i;

}

Заполняем ребра исходного графа значениями из стандартного ввода

for (int i = 0; i < m; i++){

int a, b;

cin >> a >> b;

graph[i].x = a;

graph[i].y = b;

}

Проверяем вершины каждого ребра.

Если вершины не принадлежат одному и тому же множеству,

но такое ребро добавляем в наше дерево, а вершины помещаем в одно множество

for (int i = 0; i < m; i++){

int a = graph[i].x;

int b = graph[i].y;

if (variety[a] != variety[b]){

tree.push_back(graph[i]);

int old_variety = variety[b], new_variety = variety[a];

for (int j = 0; j < n; j++){

if (variety[j] == old_variety){

variety[j] = new_variety;

}

for(int i = 0; i < n - 1; i++){ //по принципу построения дерева, оно содержит n-1 ребро

cout << tree[i].x << " " << tree[i].y;

if (i != n-2){

cout << endl;

}

return 0;

}

Тесты

Ввод	Вывод
4 4 1 2 2 3 3 4 4 1	1 2 2 3 3 4
6 7 1 2 2 3 3 4 4 5 5 6 6 1	1 2 2 3 3 4 4 5 5 6
6 5 1 2 2 3 3 4 4 5 5 6	1 2 2 3 3 4 4 5 5 6
4 5 4 3 2 4 2 3 1 2 1 3	4 3 2 4 1 2
6 9 1 2 1 3 1 5 2 5 2 4 3 5 3 6 4 5 5 6	1 2 1 3 1 5 2 4 3 6

Решение

Учитывая то, что по условию задачи нам дан связный неориентированный граф без петель и кратных ребер и то, что любое дерево с [latex]n[/latex] вершинами содержит [latex]n-1[/latex] ребро, то для получения дерева нужно удалить столько ребер, пока не останется [latex]n-1[/latex] ребро.

Данную задачу я решил, применяя упрощенный алгоритм Краскала, учитывая, что данное дерево не является взвешенным и сортировку применять не нужно. Для начала объявляем наш исходный граф используя вектор ребер (edge). Структура ребер является простой и содержит в себе только информацию о вершинах, которое ребро соединяет. Алгоритм Краскала заключается в том, что мы каждую вершину помещаем в свое множество. Затем при просмотре каждого ребра исходного графа мы проверяем принадлежат ли вершины ребра одному множеству. Если нет, то добавляем данное ребро в наше дерево (предварительно его создав с помощью вектора ребер), после добавления мы добавляем все вершины, которые принадлежали тому же множеству, что и вторая вершина ребра, в множество первой вершины. Если же вершины уже принадлежат одному множеству, то переходим к следующему этапу цикла. После этой процедуры нам достаточно вывести на экран значения из нашего дерева — это и будут необходимые ребра.

Засчитанное решение на e-olymp

Код на ideone.com

UPD: обновил код, тесты, описание решения и ссылки.

Related Images:

e-olymp 5082. Степени вершин

19/04/2016 by Сплошнов Кирилл

Условие

Задача взята с сайта e-olymp.

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

Входные данные

В первой строчке находится число [latex]1 \leq N \leq 1000[/latex] В следующих [latex]N[/latex] строчках находится матрица смежности.

Выходные данные

Выведите [latex]N[/latex] чисел – степени всех вершин.

Тесты

Ввод	Вывод
2 0 1 1 0	1 1
3 0 1 0 1 0 1 0 1 0	1 2 1
3 0 1 0 1 0 1 0 1 0	1 4 1
5 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1	6 1 6 1 6
5 0 0 1 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 0 1 0 0 0 1	1 3 4 3 3
5 0 1 1 1 1 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 1 1 1 1 0	4 1 4 1 4
5 1 0 0 0 1 0 1 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0	3 3 2 1 1

Алгоритм

Для решении задачи даже не нужно запоминать значения элементов матрицы. Выполняем данные действия [latex]N[/latex] раз, для каждой строки матрицы. Храним ответ в переменной counter, изначально [latex]0[/latex]. По очереди считываем все ее элементы и, если текущий элемент равен [latex]1[/latex], то прибавялем степени [latex]2[/latex], если элемент принадлежит главной диагонали (т.к. тогда это петля, а при подсчете степени ребро-петля учитывается дважды), иначе — [latex]1[/latex]. Затем выводим результат через пробел.

Код

#include <iostream>
using namespace std;

int main() 
{
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int counter = 0, x;
		for (int j = 0; j < n; j++)
		{
			cin >> x;
			if (x)
				counter += (i == j ? 2 : 1);
		}
		cout << counter << " ";
	}
	return 0;
}

#include <iostream>

using namespace std;

int main()

{

ios::sync_with_stdio(false);

int n;

cin >> n;

for (int i = 0; i < n; i++)

{

int counter = 0, x;

for (int j = 0; j < n; j++)

{

cin >> x;

if (x)

counter += (i == j ? 2 : 1);

}

cout << counter << " ";

}

return 0;

}

Ссылки

Засчитанное решение на e-olymp.
Код для тестирования на Ideone.

Related Images:

AL15. Лабиринт

11/04/2016 by Сплошнов Кирилл

Условие

Матрица размера [latex]n\times m[/latex] определяет некоторый лабиринт. B матрице элемент [latex]1[/latex] обозначает стену, а [latex]0[/latex] определяет свободное место. В первой строке матрицы определяются входы [latex]x_i[/latex], а в последней выходы [latex]y_i[/latex], [latex]i = 1, \ldots, k[/latex], [latex]k \leqslant n[/latex] которые должны быть нулевыми элементами.

Необходимо определить, можно ли:

а) провести [latex]k[/latex] человек от входа [latex]x_i[/latex] до выхода [latex]y_i[/latex] соответственно, [latex]i = 1, \ldots, k[/latex], таким образом, чтобы каждое свободное место посещалось не более одного раза.

б) то же, но человека можно выводить чеpез любой из выходов. Примечание: Движение в лабиринте осуществляется только по вертикали или горизонтали.

Входные данные

Числа [latex]n[/latex] и [latex]m[/latex] определяющие кол-во строк и столбцов соответственно, [latex]1 \leqslant n, m \leqslant 10^4[/latex]. Количество входов [latex]k[/latex] равно кол-ву выходов, [latex]1 \leqslant k \leqslant \min(1000, n)[/latex]. Число [latex]k[/latex] не является частью входных данных (не подается на вход программы).

Выходные данные

[latex]YES[/latex], если соответствующий набор маршрутов существует, [latex]NO[/latex] — в противном случае.

Замечания

Легко заметить, что случай б) эквивалентен случаю а). Предположим, что [latex]k > 1[/latex] и мы провели первых [latex]i — 1[/latex] людей (возможно, никого) согласно условию а), [latex]1 \leqslant i < k[/latex]. Пусть человек под номером [latex]i[/latex] нарушил условие, например, вышел через выход с номером [latex]i + 1[/latex]. Тогда, т.к. его путь цельный и идет от самого первого ряда лабиринта до последнего, он образует «стену» из единичек, заблокировав выход [latex]i[/latex]. Тогда провести всех людей не возможно, ведь кол-ва входов и выходов равны. Следовательно, будем рассматривать как нашу задачу только случай а).
Заполнение клеток каждого из пройденных маршрутов в матрице различными числами вместо единицы и функция

C++

void print(int n, int m, int** matrix)

1

void print(int n, int m, int** matrix)

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

Тесты

№ теста	Входные данные	Выходные данные	Пояснение (маршрут)
1	6 8 1 0 1 0 1 1 0 1 1 0 1 0 0 0 0 1 1 0 1 1 0 0 1 1 1 0 0 0 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 0 1	YES	1 a 1 b 1 1 c 1 1 a 1 b b c c 1 1 a 1 1 b c 1 1 1 a b b b c 0 1 1 a b 1 1 c c 1 1 a b 1 1 1 c 1
2	5 7 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 0	YES	1 a b c 1 1 d a a b c d d d a b b c d 1 1 a b c c d d d a b c 1 1 1 d
3	7 7 1 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 1 0 1 0	YES	1 1 a b 1 1 1 a a a b 0 0 0 a a b b 0 0 0 1 a b b b b 0 a a a a a b 0 a a a 1 a b b 1 1 1 1 a 1 b
4	5 5 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0	NO
5	7 12 1 1 1 1 1 0 1 1 1 1 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 1 0 0 1 1 0 0 0 1 1 1 0 0 0 1 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0	YES	1 1 1 1 1 a 1 1 1 1 1 b 0 0 0 1 a a 1 0 0 0 0 b 0 0 0 a a 1 1 0 1 1 1 b 0 1 1 a 0 0 1 1 1 0 0 b 1 0 1 a 0 0 1 0 0 0 1 b 0 0 0 a a a 1 0 0 1 1 b 1 1 1 1 1 a 1 1 1 1 1 b
6	3 6 1 1 1 1 1 0 0 0 0 0 0 0 1 0 1 1 1 1	YES	1 1 1 1 1 a 0 a a a a a 1 a 1 1 1 1
7	10 10 0 1 1 1 1 1 1 1 1 1 0 1 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1 1 1 0 0 1 0 1 0 0 0 0 1 0 0 1 0 1 0 0 1 0 1 0 0 1 0 1 0 0 1 0 1 0 0 1 0 0 0 0 1 0 1 0 0 1 1 1 1 1 1 0 1 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1 1 1 1 1 1 0	YES	a 1 1 1 1 1 1 1 1 1 a 1 a a a a a a a a a 1 a 1 1 1 1 1 1 a a 1 a 1 a a a a 1 a a 1 a 1 a 0 1 a 1 a a 1 a 1 a 0 1 a 1 a a 1 a a a 0 1 a 1 a a 1 1 1 1 1 1 a 1 a a a a a a a a a 1 a 1 1 1 1 1 1 1 1 1 a
8	10 10 0 1 1 1 1 1 1 1 1 1 0 1 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1 1 1 0 0 1 0 1 0 0 0 0 1 0 0 1 0 1 1 0 1 0 1 0 0 1 0 1 0 1 1 0 1 0 0 1 0 0 0 0 1 0 1 0 0 1 1 1 1 1 1 0 1 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1 1 1 1 1 1 0	NO
9	6 7 1 1 1 1 0 0 1 0 0 0 1 0 0 1 0 1 0 0 0 0 1 0 0 1 0 0 0 1 1 0 0 0 0 1 1 1 1 0 0 1 1 1	YES	1 1 1 1 a b 1 a a a 1 a b 1 a 1 a a a b 1 a a 1 b b b 1 1 a a b 0 1 1 1 1 a b 1 1 1
10	1 5 0 0 0 0 0	YES	a b c d e

Алгоритм

Оптимальной стратегией будет оставлять как можно больше места последующим людям, т.е. для каждого из людей всегда стараться занять либо самые левые, либо самые правые места, «держась» при этом стены лабиринта. Для удобства, будем рассматривать стратегию «поиска влево». Считаем матрицу чисел, и для каждого входа необходимо будет:

Попытаться провести человека согласно описанной выше стратегии.
В случае успеха, отметить все ячейки, пройденные ним, как недоступные. Иначе — будем кидать исключение, ловить которое будем непосредственно в основной функции, при поимке — выводим [latex]NO[/latex] и завершаем работу программы.

За поиск маршрута отвечают 2 функции. Функция

stack<pair<int,int>> findRoute(int n, int m, int** matrix, int begin)

1	stack<pair<int,int>> findRoute(int n, int m, int** matrix, int begin)

возвращает стек координат (пар чисел), представляющих собой маршрут человека, или кидает исключение в случае его отсутствия. Функция только создает стек, помещает в него первую вершину и запускает рекурсивную функцию

bool search(int n, int m, int** matrix, stack<pair<int,int>>& route, int dir)

1	bool search(int n, int m, int** matrix, stack<pair<int,int>>& route, int dir)

отвечающую непосредственно за поиск, из точки входа с направлением движения вниз (т.к. из входа первый шаг можно совершить только вниз). Алгоритм поиска маршрута:

Находим, в какую клетку мы попали при данном направлении. Определим все направления как подходящие константы и будем получать направление по формуле [latex]dir / 10, dir \mod 10[/latex], первая координата — по вертикали, вторая — по горизонтали. Так, например, для [latex]down = 10[/latex] получим вектор [latex](1, 0)[/latex], соответствующий перемещению на одну ячейку вниз в матрице (для остальных направлений значения подобраны аналогично).
Проверяем, можем ли мы находиться в этой ячейке, если нет (она занята или находится вне матрицы) — не ищем дальше, возвращаем [latex]false[/latex].
Добавляем координаты ячейки в стек route, проверяем, является ли данная точка выходом, если да — завершаем поиск успешно ([latex]true[/latex]).
Составим массив направлений, от наиболее до наименее приоритетных, в зависимости от предыдущего направления. Например, текущее направление было [latex]down[/latex], мы пришли сверху, лучше всего будет попробовать пойти влево, иначе снова вниз, иначе вправо, наверх нельзя (уже были):

C++

priorityDirs = new int[3]{left, down, right};

42

priorityDirs = new int[3]{left, down, right};

Для других направлений — рассуждения аналогичны.
Поочередно вызовем поиск из новой точки в каждом из направлений в порядке приоритета, при нахождении пути оставшиеся направления (с меньшим приоритетом) не рассматриваем, возвращаем [latex]true[/latex].
Если ни в одном из направлений нельзя попасть к выходу (тупик) — удаляем вершину из стека, возвращаем [latex]false[/latex].

Код

#include <iostream>
#include <stack>
#include <utility>
#define down 10
#define left -1
#define right 1
#define up -10
using namespace std;

void print(int n, int m, int** matrix)
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (matrix[i][j] == 0 || matrix[i][j] == 1)
                cout << matrix[i][j] << " ";
            else
                cout << (char)matrix[i][j] << " ";
        }
        cout << endl;
    }
}

bool search(int n, int m, int** matrix, stack<pair<int,int>>& route, int dir)
{
    pair<int, int> npos = make_pair(dir / 10 + route.top().first, dir % 10 + route.top().second);
    if (npos.first < 0 || npos.first >= n || npos.second < 0 || npos.second >= m || matrix[npos.first][npos.second] != 0)
        return false;
    else
    {
        route.push(npos);
        matrix[npos.first][npos.second] = 1; //чтобы при построении маршрута нельзя было вернутся в предыдущие вершины
        if (npos.first == n - 1)
            return true;
        else
        {
            int* priorityDirs;
            switch (dir)
            {
                case down:
                    priorityDirs = new int[3]{left, down, right};
                    break;
                case left:
                    priorityDirs = new int[3]{left, down, up};
                    break;
                case right:
                    priorityDirs = new int[3]{down, right, up};
                    break;
                case up:
                    priorityDirs = new int[3]{left, right, up};
                    break;
            }
            bool found = true;
            for (int i = 0; i < 3; i++)
            {
                found = search(n, m, matrix, route, priorityDirs[i]);
                if (found)
                    return true;
            }
            matrix[npos.first][npos.second] = 0; //если ячейка не подходит, убираем ее из маршрута (освобождаем)
            route.pop();
            return false;
        }
    }
}

stack<pair<int,int>> findRoute(int n, int m, int** matrix, int begin)
{
    stack<pair<int,int>> route;
    route.push(make_pair(0, begin));
    if (n != 1 && !search(n, m, matrix, route, down)) //n != 1 для корректного ответа на тесты вида №10
        throw -1;
    return route;
}

int main() 
{
    ios::sync_with_stdio(false);
    int n, m;
    scanf("%d%d", &n, &m);
    int** matrix = new int*[n];
    for (int i = 0; i < n; i++)
        matrix[i] = new int[m];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            scanf("%d", &matrix[i][j]);
    bool possible = true;
    int symbol = -1; //определяет символ, которым будет отмечен маршрут человека при необходимости вывода лабиринта на экран
    for (int i = 0; i < m; i++)
    {
        if (matrix[0][i] == 0)
        {
            symbol++;
            try
            {
                stack<pair<int,int>> route = findRoute(n, m, matrix, i);
                while (!route.empty()) //вынимаем из стека координаты пройденных ячеек и отмечаем их в матрице
                {
                    pair<int, int> pos = route.top(); 
                    matrix[pos.first][pos.second] = 'a' + symbol; //для удобства при необходимости вывода маршрута
                    route.pop();
                }
            }
            catch (...)
            {
                possible = false;
                break;
            }
        }
    }
    cout << (possible ? "YES" : "NO") << endl;
    /*
    if (possible)
        print(n, m, matrix);
    */
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

#include <iostream>

#include <stack>

#include <utility>

#define down 10

#define left -1

#define right 1

#define up -10

using namespace std;

void print(int n, int m, int** matrix)

{

for (int i = 0; i < n; i++)

{

for (int j = 0; j < m; j++)

{

if (matrix[i][j] == 0 || matrix[i][j] == 1)

cout << matrix[i][j] << " ";

else

cout << (char)matrix[i][j] << " ";

}

cout << endl;

}

bool search(int n, int m, int** matrix, stack<pair<int,int>>& route, int dir)

{

pair<int, int> npos = make_pair(dir / 10 + route.top().first, dir % 10 + route.top().second);

if (npos.first < 0 || npos.first >= n || npos.second < 0 || npos.second >= m || matrix[npos.first][npos.second] != 0)

return false;

else

{

route.push(npos);

matrix[npos.first][npos.second] = 1; //чтобы при построении маршрута нельзя было вернутся в предыдущие вершины

if (npos.first == n - 1)

return true;

else

{

int* priorityDirs;

switch (dir)

{

case down:

priorityDirs = new int[3]{left, down, right};

break;

case left:

priorityDirs = new int[3]{left, down, up};

break;

case right:

priorityDirs = new int[3]{down, right, up};

break;

case up:

priorityDirs = new int[3]{left, right, up};

break;

}

bool found = true;

for (int i = 0; i < 3; i++)

{

found = search(n, m, matrix, route, priorityDirs[i]);

if (found)

return true;

}

matrix[npos.first][npos.second] = 0; //если ячейка не подходит, убираем ее из маршрута (освобождаем)

route.pop();

return false;

}

stack<pair<int,int>> findRoute(int n, int m, int** matrix, int begin)

{

stack<pair<int,int>> route;

route.push(make_pair(0, begin));

if (n != 1 && !search(n, m, matrix, route, down)) //n != 1 для корректного ответа на тесты вида №10

throw -1;

return route;

}

int main()

{

ios::sync_with_stdio(false);

int n, m;

scanf("%d%d", &n, &m);

int** matrix = new int*[n];

for (int i = 0; i < n; i++)

matrix[i] = new int[m];

for (int i = 0; i < n; i++)

for (int j = 0; j < m; j++)

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

bool possible = true;

int symbol = -1; //определяет символ, которым будет отмечен маршрут человека при необходимости вывода лабиринта на экран

for (int i = 0; i < m; i++)

{

if (matrix[0][i] == 0)

{

symbol++;

try

{

stack<pair<int,int>> route = findRoute(n, m, matrix, i);

while (!route.empty()) //вынимаем из стека координаты пройденных ячеек и отмечаем их в матрице

{

pair<int, int> pos = route.top();

matrix[pos.first][pos.second] = 'a' + symbol; //для удобства при необходимости вывода маршрута

route.pop();

}

catch (...)

{

possible = false;

break;

}

cout << (possible ? "YES" : "NO") << endl;

if (possible)

print(n, m, matrix);

return 0;

}

Ссылки

Код для тестирования на ideone.

Related Images:

e-olymp 4002. Down with cheating!

10/04/2016 by Таран Таня

During the test, Professor Floyd noticed that some students exchanged notes. At first, he wanted to put a bad mark everyone, but that day the professor was in a good mood, therefore he decided to split all the students into two groups and put a bad mark to only those,who writting off.
The professor recorded all the pairs of students, who exchanged notes. You need to determine whether they can be divided into two groups, where student of one group exchange notes only with student of other group.

Input

There are two numbers in first line [latex]m[/latex] and [latex]n[/latex] — quantity of students and quantity of pairs, who exchanged notes. [latex](1 \le n \le 100[/latex], [latex]0 \le m \le n(n-1)/2)[/latex]. Further in [latex]m[/latex] lines there are description of student pairs: two different numbers, corresponding to the student serial number, who exchanged notes (numbering from [latex]1[/latex]). Each pair of students is listed only once.

Output

Print the answer to the Professor’s Floyd task. If it is possible to divide the students into two groups output «YES», or «NO» otherwise.

Test

№	Input	Output
1	3 2 1 2 2 3	YES
2	3 3 1 2 1 3 2 3	NO
3	12 9 1 3 2 3 4 5 5 6 6 8 6 9 7 9 8 10 11 12	*YES*
4	12 10 1 3 2 3 4 5 5 6 6 8 6 9 7 9 8 9 8 10 11 12	NO

Illustration for the test №3
Illustration for the test №4

Algorithm

After reading the statement of the problem becomes clear that our goal is to determine whether it is possible to divide the graph into two sets in each of them there aren’t adjacent vertices — check whether the graph is bipartite.
For the implementation, we need a basic function
bool isBipartite(vector<int> *listOfVertices, int *colorOfVertices, int sourceVertex, int quantityOfVertex), that takes a graph (in this program as an array of vectors of adjacent vertices, but can be done similar implementation on the adjacency matrix), array of vertices’ colors, vertex, which we start checking, and the number of vertices.
To solve the problem we perform graph coloring. Naturally, we organize data reading process. And our next sequence of steps is:

Initially, we define all the vertices as WHITE — not processed.
Call the fucntion for the first vertex (in our numbering — zero).
Assign source vertex with one of the colors (for convenience in program we denote it as RED) — equivalent to the action that we put the vertex in the first of two sets.
Color all adjacent vertex with inverse color (in program it’s BLUE — has opposite to RED number value) — equivalent to the action that we put vertices in the second set.
Color all adjacent to the adjacent vertices with RED color — we put them in the first set.
Repeat this until we have completed bypassing (for convenience we use queue) — coloring of all connected vertices. But we can find adjacent vertices with same color that sygnalize that our graph cannot be colored with two color — so it isn’t bipartite.

It should be noted that the function implemented in such way works for only one connected component. Therefore, to check the disconnected graphs we must check all vertices which color is white.

Code

#define RED -1																							// First set of vertices
#define BLUE 1																							// Second set of vertices
#define WHITE 0																							// Not processed vertices
#include <queue>
#include <vector>
#include <iostream>
using namespace std;

bool isBipartite(vector<int> *listOfVertices, int *colorOfVertices, int sourceVertex, int quantityOfVertex) {
	bool isBipartite = true;
	colorOfVertices[sourceVertex] = RED;																    //	Color vertex which we started
	queue <int> orderOfBypassing;																		//	Stores order of bypassing with queue
	orderOfBypassing.push(sourceVertex);																    //  Remember the initial vertex
	while (!orderOfBypassing.empty()) {																	//	Process until we bypass all connected vertices
		int currentVertex = orderOfBypassing.front();													//	Remember vertex that came first in queue
		orderOfBypassing.pop();																			//	Remove it
		for (auto adjacentVertex : listOfVertices[currentVertex]) {										//	Process all adjacent with current and not processed earlier vertices
			if (colorOfVertices[adjacentVertex] == WHITE) {
				colorOfVertices[adjacentVertex] = -colorOfVertices[currentVertex];						//	Color adjacent vertex with inverse color
				orderOfBypassing.push(adjacentVertex);													//	Add this vertex to the order of bypass
			}
			else if (colorOfVertices[adjacentVertex] == colorOfVertices[currentVertex]) {				//	If two adjacent vertices in one set are the same color
				isBipartite = false;																	    //	Graph isn't bipartite
				break;																					//	We can stop processing
			}
		}
	}
	return isBipartite;
}

int main() {
	bool answer = true;
	int quantityOfVertex, quantityOfConnections;
	cin >> quantityOfVertex >> quantityOfConnections;
	vector<int> *listOfVertices = new vector<int>[quantityOfVertex];									    //	Stores for the each vertex adjacent vertices
	while (quantityOfConnections--) {																	//	Read all given connections
		int firstVertex, secondVertex;
		cin >> firstVertex >> secondVertex;
		firstVertex--;																					//	We store it numbering from zero, so decrement index of vertices
		secondVertex--;
		listOfVertices[firstVertex].push_back(secondVertex);											    //	Add vertex to the vector of adjacent vertex
		listOfVertices[secondVertex].push_back(firstVertex);											    //	Do it symmetrically
	}
	int *colorOfVertices = new int[quantityOfVertex];													//	For each vertex stores it's color
	for (int indexOfVertex = 0; indexOfVertex < quantityOfVertex; indexOfVertex++) {
		colorOfVertices[indexOfVertex] = WHITE;															//	Intially, all vertices are white (not processed)
	}
	for (int indexOfVertex = 0; indexOfVertex < quantityOfVertex && answer; indexOfVertex++) {			//	Process to the end or until we recognize, that graph isn't bipartite
		if (colorOfVertices[indexOfVertex] == WHITE) {													//	Process only WHITE vertices
			answer &= isBipartite(listOfVertices, colorOfVertices, indexOfVertex, quantityOfVertex);	    //	Logical conjunction of answers for all graph component 
		}
	}
	cout << (answer ? "YES" : "NO");
	return 0;
}

#define RED -1 // First set of vertices

#define BLUE 1 // Second set of vertices

#define WHITE 0 // Not processed vertices

#include <queue>

#include <vector>

#include <iostream>

using namespace std;

bool isBipartite(vector<int> *listOfVertices, int *colorOfVertices, int sourceVertex, int quantityOfVertex) {

bool isBipartite = true;

colorOfVertices[sourceVertex] = RED; // Color vertex which we started

queue <int> orderOfBypassing; // Stores order of bypassing with queue

orderOfBypassing.push(sourceVertex); // Remember the initial vertex

while (!orderOfBypassing.empty()) { // Process until we bypass all connected vertices

int currentVertex = orderOfBypassing.front(); // Remember vertex that came first in queue

orderOfBypassing.pop(); // Remove it

for (auto adjacentVertex : listOfVertices[currentVertex]) { // Process all adjacent with current and not processed earlier vertices

if (colorOfVertices[adjacentVertex] == WHITE) {

colorOfVertices[adjacentVertex] = -colorOfVertices[currentVertex]; // Color adjacent vertex with inverse color

orderOfBypassing.push(adjacentVertex); // Add this vertex to the order of bypass

}

else if (colorOfVertices[adjacentVertex] == colorOfVertices[currentVertex]) { // If two adjacent vertices in one set are the same color

isBipartite = false; // Graph isn't bipartite

break; // We can stop processing

}

return isBipartite;

}

int main() {

bool answer = true;

int quantityOfVertex, quantityOfConnections;

cin >> quantityOfVertex >> quantityOfConnections;

vector<int> *listOfVertices = new vector<int>[quantityOfVertex]; // Stores for the each vertex adjacent vertices

while (quantityOfConnections--) { // Read all given connections

int firstVertex, secondVertex;

cin >> firstVertex >> secondVertex;

firstVertex--; // We store it numbering from zero, so decrement index of vertices

secondVertex--;

listOfVertices[firstVertex].push_back(secondVertex); // Add vertex to the vector of adjacent vertex

listOfVertices[secondVertex].push_back(firstVertex); // Do it symmetrically

}

int *colorOfVertices = new int[quantityOfVertex]; // For each vertex stores it's color

for (int indexOfVertex = 0; indexOfVertex < quantityOfVertex; indexOfVertex++) {

colorOfVertices[indexOfVertex] = WHITE; // Intially, all vertices are white (not processed)

}

for (int indexOfVertex = 0; indexOfVertex < quantityOfVertex && answer; indexOfVertex++) { // Process to the end or until we recognize, that graph isn't bipartite

if (colorOfVertices[indexOfVertex] == WHITE) { // Process only WHITE vertices

answer &= isBipartite(listOfVertices, colorOfVertices, indexOfVertex, quantityOfVertex); // Logical conjunction of answers for all graph component

}

cout << (answer ? "YES" : "NO");

return 0;

}

Related Images:

e-olymp 4003. Топологическая сортировка

26/03/2016 by Сплошнов Кирилл

Задача взята отсюда.

Условие

Дан ориентированный невзвешенный граф. Необходимо его топологически отсортировать.

Входные данные

В первой строке содержатся два натуральных числа [latex]n[/latex] и [latex]m[/latex] ([latex]1 \leq n \leq 10^5[/latex], [latex]1 \leq m \leq 10^5[/latex]) — количество вершин и рёбер в графе соответственно. Далее в [latex]m[/latex] строках перечислены рёбра графа. Каждое ребро задаётся парой чисел — номерами начальной и конечной вершин соответственно.

Выходные данные

Вывести любую топологическую сортировку графа в виде последовательности номеров вершин. Если граф невозможно топологически отсортировать, требуется вывести [latex]-1[/latex].

Решение

Для решения использовался алгоритм топологической сортировки методом поиска в глубину (подробнее в комментариях к коду). Функция bool dfs() (поиск в глубину) также проверяет, цикличен ли граф, т.к. по условию он может как содержать, так и не содержать циклы. Результат сортировки заносим в вектор result, потом выводим его элементы по порядку.

Тесты

№	Входные данные	Выходные данные
1	6 6 1 2 3 2 4 2 2 5 6 5 4 6	4 6 3 1 2 5
2	3 3 1 2 2 3 3 1	-1
3	4 4 1 4 4 3 3 2 4 2	1 4 3 2

Код

#include <iostream>
#include <vector>
#include <algorithm>
#define WHITE 0 //вершина не посещена
#define GREY 1 //вершина обрабатывается
#define BLACK 2 //вершина обработана
using namespace std;

bool dfs (int v, vector<int>* vertex, int* state, vector<int> &result, int size) //возвращает true или false в зависимости от того, был ли найден цикл
{
	state[v] = GREY; //отмечаем, что вершина в процессе обработки
	for (int i = 0; i < vertex[v].size(); i++) //для каждой вершины, в которую можно попасть из данной
	{
		int dest = vertex[v].at(i);
		if (state[dest] == WHITE) //если еще не посетили - запускаем поиск в глубину, возвращаем true, если далее был найден цикл
		{
			if (dfs(dest, vertex, state, result, size))
				return true;
		}
		else if (state[dest] == GREY) //если из вершины можно попасть туда, где мы уже были при данном порядке обхода - найден цикл
		{
			return true;
		}
	}
    //если цикл не найден:
	state[v] = BLACK; //помечаем вершину как обработанную
	result.push_back(v+1); //помещаем ее номер (со сдвигом на 1, из-за разницы в нумерациях) в вектор-результат сортировки
	return false;
}

void topologicalSort(vector<int>* vertex, int* state, vector<int> &result, int size)
{
	for (int i = 0; i < size; i++) //для каждой вершины графа
	{
		if (state[i] == WHITE) //если она еще не посещена
		{
			bool cyclic = dfs(i, vertex, state, result, size); //вызываем для нее поиск в глубину
			if (cyclic) //если нашли цикл, возвращаем единственное значение -1 (по условию)
			{
				result.clear();
				result.push_back(-1);
				return;
			}
		}
	}
	reverse(result.begin(), result.end()); //вершины добавляются в вектор в порядке, противоположном топологической сортировке, так что нужно вызвать для вектора reverse()
}

int main() 
{
	ios::sync_with_stdio(false); 
	int n, m;
	cin >> n >> m;
	vector<int> vertex[n]; //сам граф
	int state[n]; //массив состояний вершин
	vector<int> result;
	fill (state, state + n, WHITE); //изначально ни одна вершина не посещена
	for (int i = 0; i < n; i++)
	{
		int begin, end;
		cin >> begin >> end;
		vertex[begin-1].push_back(end-1);
	}
	topologicalSort(vertex, state, result, n); //сортируем граф
	for (int i = 0; i < result.size(); i++)
		cout << result.at(i) << " ";
	return 0;
}

#include <iostream>

#include <vector>

#include <algorithm>

#define WHITE 0 //вершина не посещена

#define GREY 1 //вершина обрабатывается

#define BLACK 2 //вершина обработана

using namespace std;

bool dfs (int v, vector<int>* vertex, int* state, vector<int> &result, int size) //возвращает true или false в зависимости от того, был ли найден цикл

{

state[v] = GREY; //отмечаем, что вершина в процессе обработки

for (int i = 0; i < vertex[v].size(); i++) //для каждой вершины, в которую можно попасть из данной

{

int dest = vertex[v].at(i);

if (state[dest] == WHITE) //если еще не посетили - запускаем поиск в глубину, возвращаем true, если далее был найден цикл

{

if (dfs(dest, vertex, state, result, size))

return true;

}

else if (state[dest] == GREY) //если из вершины можно попасть туда, где мы уже были при данном порядке обхода - найден цикл

{

return true;

}

//если цикл не найден:

state[v] = BLACK; //помечаем вершину как обработанную

result.push_back(v+1); //помещаем ее номер (со сдвигом на 1, из-за разницы в нумерациях) в вектор-результат сортировки

return false;

}

void topologicalSort(vector<int>* vertex, int* state, vector<int> &result, int size)

{

for (int i = 0; i < size; i++) //для каждой вершины графа

{

if (state[i] == WHITE) //если она еще не посещена

{

bool cyclic = dfs(i, vertex, state, result, size); //вызываем для нее поиск в глубину

if (cyclic) //если нашли цикл, возвращаем единственное значение -1 (по условию)

{

result.clear();

result.push_back(-1);

return;

}

reverse(result.begin(), result.end()); //вершины добавляются в вектор в порядке, противоположном топологической сортировке, так что нужно вызвать для вектора reverse()

}

int main()

{

ios::sync_with_stdio(false);

int n, m;

cin >> n >> m;

vector<int> vertex[n]; //сам граф

int state[n]; //массив состояний вершин

vector<int> result;

fill (state, state + n, WHITE); //изначально ни одна вершина не посещена

for (int i = 0; i < n; i++)

{

int begin, end;

cin >> begin >> end;

vertex[begin-1].push_back(end-1);

}

topologicalSort(vertex, state, result, n); //сортируем граф

for (int i = 0; i < result.size(); i++)

cout << result.at(i) << " ";

return 0;

}

Ссылки

Код на ideaone.

Засчитанное решение на e-olymp.

Наглядное объяснение топологической сортировки здесь.

Related Images:

e-olymp 4050. Забавная игра

29/06/2015 by Зелінський Вячеслав Олександрович

Ссылка на задачу.

Засчитанное решение.

В одной стране есть несколько аэропортов, между некоторыми аэропортами есть рейсы. Можно перелететь из любого аэропорта в любой другой, возможно, с несколькими пересадками. Для каждой пары аэропортов существует только одна последовательность рейсов, соединяющая эти аэропорты.

Два террориста играют в игру. Они делают ходы по очереди. Каждый ход заключается в следующих действиях. Игрок минирует аэропорт, выбирает рейс и улетает вместе со своим коллегой. После взлёта он активирует радиоуправляемый взрыватель. В результате аэропорт, который только что покинули террористы, разрушен, и рейсы в этот аэропорт и из него больше невозможны. После того, как самолёт приземляется, другой игрок делает ход — и дальше по очереди. Проигрывает тот, кто не может сделать ход.

Напишите программу, которая по начальному списку полётов и номеру аэропорта, в котором террористы начинают игру, определяет, кто выигрывает, если террористы играют идеально (каждый выбирает лучший ход).

Входные данные

Первая строка содержит два целых числа: n и k, разделённые пробелом. Здесь n — количество аэропортов (n ≤1000), а k — номер аэропорта, являющегося начальной точкой игры (1 ≤ k ≤ n). Следующая n−1 строка содержит пары целых чисел, разделённых пробелами. Это номера аэропортов, соединённых рейсом. Все рейсы двусторонние и упомянуты только один раз. Каждый аэропорт соединён рейсами не более, чем с 20 другими.

Выходные данные

Если игрок, начинающий игру, выигрывает, программа должна написать «First player wins flying to airport L«, где L— номер аэропорта, в который игрок должен вылететь из текущего. Если таких аэропортов несколько, программа должна выбрать вариант с меньшим номером аэропорта. Если начинающий игрок проигрывает, программа должна написать «First player loses«.

#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
bool is_use[1001];
vector<int> airports[1001];
int level = 0;					// уровень вложенности dfs
/*int isFindAnsver = false;		// переменная выхода из цикла*/
int second_ver = 0;					// переменная запоминает вторую вершину, для ответа
bool is_second_ver_find = false;
bool is_sort[1001];
bool FIRST_WIN = true, SECOND_WIN = false;
 
bool dfs(int now_ver){			// Возвращает true если выигрывает первы, и false, если второй
	is_use[now_ver] = true;
	bool child;
	level++;
	if(level == 2){
		second_ver = now_ver;
	}
	if(!is_sort[now_ver]){
		sort(airports[now_ver].begin(), airports[now_ver].end());
		is_sort[now_ver] = true;
	}
 
	int count_ver=0;				// переменная считает вершины в которые можно пойти из данной
	for(int i=0 ; i<airports[now_ver].size() ; i++ ){			// 
		if( !is_use[ airports[now_ver][i] ] ){
			// В зависимости от четноси мы должны искать тот ли иной овет
			// от четности зависит то каккой игрок ходит на данный момент
			child = dfs(airports[now_ver][i]);
			// Если нечетное, то мы ищем правильных ход первого, иначе правильный ход второго
			if(level%2 == 1? child == FIRST_WIN : child == SECOND_WIN){		
				if(level == 1){
					if(child == FIRST_WIN){
						cout << "First player wins flying to airport " << second_ver << endl;
					}else{		// SECOND_WIn
						cout << "First player loses" << endl;
					}
					return true;
				}else{
					level--;
					return child;
				}
			}	// если найден нужный нам ответ на этом уровне
 
			count_ver++;
		}
	}
 
	is_use[now_ver] = false;
	
 
	if(level != 1)return ((level--)%2 == 1? SECOND_WIN : FIRST_WIN);			
	else{
		if(child == FIRST_WIN){
			cout << "First player wins flying to airport " << second_ver << endl;
		}else{		
			cout << "First player loses" << endl;
		}
	}
}
 
 
 
int main(){
	int n, k;
	cin >> n >> k;
	int u, v;
	for( int i=0 ; i<n-1 ; i++ ){			
		cin >> u >> v;
		airports[u].push_back(v);
		airports[v].push_back(u);
	}
 
	second_ver = k;
 
	dfs(k);
}

#include <cstdlib>

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

bool is_use[1001];

vector<int> airports[1001];

int level = 0; // уровень вложенности dfs

/*int isFindAnsver = false; // переменная выхода из цикла*/

int second_ver = 0; // переменная запоминает вторую вершину, для ответа

bool is_second_ver_find = false;

bool is_sort[1001];

bool FIRST_WIN = true, SECOND_WIN = false;

bool dfs(int now_ver){ // Возвращает true если выигрывает первы, и false, если второй

is_use[now_ver] = true;

bool child;

level++;

if(level == 2){

second_ver = now_ver;

}

if(!is_sort[now_ver]){

sort(airports[now_ver].begin(), airports[now_ver].end());

is_sort[now_ver] = true;

}

int count_ver=0; // переменная считает вершины в которые можно пойти из данной

for(int i=0 ; i<airports[now_ver].size() ; i++ ){ //

if( !is_use[ airports[now_ver][i] ] ){

// В зависимости от четноси мы должны искать тот ли иной овет

// от четности зависит то каккой игрок ходит на данный момент

child = dfs(airports[now_ver][i]);

// Если нечетное, то мы ищем правильных ход первого, иначе правильный ход второго

if(level%2 == 1? child == FIRST_WIN : child == SECOND_WIN){

if(level == 1){

if(child == FIRST_WIN){

cout << "First player wins flying to airport " << second_ver << endl;

}else{ // SECOND_WIn

cout << "First player loses" << endl;

}

return true;

}else{

level--;

return child;

}

} // если найден нужный нам ответ на этом уровне

count_ver++;

}

is_use[now_ver] = false;

if(level != 1)return ((level--)%2 == 1? SECOND_WIN : FIRST_WIN);

else{

if(child == FIRST_WIN){

cout << "First player wins flying to airport " << second_ver << endl;

}else{

cout << "First player loses" << endl;

}

int main(){

int n, k;

cin >> n >> k;

int u, v;

for( int i=0 ; i<n-1 ; i++ ){

cin >> u >> v;

airports[u].push_back(v);

airports[v].push_back(u);

}

second_ver = k;

dfs(k);

}

Определяем массив аэропортов, булев массив пройденных аэропортов уровень вложенности функции dfs(), переменную запоминающую вторую вершину, булевы переменные для определения победителя, отсортированных вершин. В функции мы отмечаем первую вершину как пройденную переходим на следующий уровень. Сортируем все возможные варианты перехода, выбираем наименьший подходящий нам. Далее определяем переменную, которая считает вершины, в которые можно пойти из данной. В цикле проходим все вершины, пока проходим считаем количество детей.
Если оно равно нулю то это тупик.
И мы посмотрим кто бы выиграл если бы бандиты дошли до этого аэропорта.Если level нечетный, то мы ищем правильный ход первого, иначе второго террориста. Если уровень равен 1, то мы уже выходим. Выводим ответ. Иначе, если level не равен 1, то мы еще не дошли до конца и возвращаем выше, кто выигрывает в данном узле.
При этом каждый бандит ищет ветку где бы он победил.
Определяем количество детей. Если мы не в тупике, то но увеличивается на 1. Далее, если ходит второй террорист, то он выбирает ветку, в котором выиграет он. Если мы попали в тупик, выводим кто выиграл в зависимости от четности пройденного пути.
В main() считываем количество аэропортов и номер первого , записываем в вектора смежные аэропорты для каждого и запоминаем первую вершину. Запускаем dfs().

Related Images:

e-olymp 1454. Лабиринт знаний

28/06/2015 by Ковальський Олександр Дмитрович

Задача

В Летней Компьютерной Школе (ЛКШ) построили аттракцион «Лабиринт знаний». Лабиринт представляет собой n комнат, занумерованных от 1 до n, между некоторыми из которых есть двери. Когда человек проходит через дверь, показатель его знаний изменяется на определенную величину, фиксированную для данной двери. Вход в лабиринт находится в комнате 1, выход — в комнате n. Каждый ученик проходит лабиринт ровно один раз и попадает в ту или иную учебную группу в зависимости от количества набранных знаний (при входе в лабиринт этот показатель равен нулю). Ваша задача показать наилучший результат.

Пример

Входные данные	Выходные данные
2 2 1 2 5 1 2 -5	5
5 5 1 2 5 2 4 5 4 5 5 3 3 5 2 3 5	15
3 3 1 2 5 1 2 -5 2 2 6	🙁
3 3 1 2 2 2 3 3 3 1 4	🙂

Решение

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

struct edge
	{
		int start,finish,cost;
	};
	
int main()
	{
		int n,m;
		cin>>n>>m;
		vector<edge>e;
		for (int i=0;i<m;i++)
			{
				edge a;
				cin>>a.start>>a.finish>>a.cost;
				a.start--;
				a.finish--;
				e.push_back(a);
			}
		vector<int> length (n, INT_MIN);
		vector<int> p (n, -1);
		length[0] = 0;
		int x;
		for (int i=0;i<n;i++)
			{
				x = -1;
				for (int j=0;j<m;j++)
					if ((length[e[j].start]>INT_MIN)&&(length[e[j].finish]<length[e[j].start] + e[j].cost))
							{
								length[e[j].finish]=length[e[j].start] + e[j].cost;
								p[e[j].finish]=e[j].start;
								x=1;
							}
			}
		vector<int> path;
		int k=0;
		for (int i=n-1;i!=-1;i=p[i])
			{
				k++;
				path.push_back (i);
				if(k>n) break;
			}
		if(length[n-1]==INT_MIN) cout<<":("<<endl;
		else 
			 if((x!=-1)&&((path.back()!=0)||(path.front()!=n-1)||(k>n))) cout<<":)"<<endl;
			 else cout<<length[n-1]<<endl;
		return 0;
	}

#include <iostream>

#include <vector>

#include <climits>

using namespace std;

struct edge

{

int start,finish,cost;

};

int main()

{

int n,m;

cin>>n>>m;

vector<edge>e;

for (int i=0;i<m;i++)

{

edge a;

cin>>a.start>>a.finish>>a.cost;

a.start--;

a.finish--;

e.push_back(a);

}

vector<int> length (n, INT_MIN);

vector<int> p (n, -1);

length[0] = 0;

int x;

for (int i=0;i<n;i++)

{

x = -1;

for (int j=0;j<m;j++)

if ((length[e[j].start]>INT_MIN)&&(length[e[j].finish]<length[e[j].start] + e[j].cost))

{

length[e[j].finish]=length[e[j].start] + e[j].cost;

p[e[j].finish]=e[j].start;

x=1;

}

vector<int> path;

int k=0;

for (int i=n-1;i!=-1;i=p[i])

{

k++;

path.push_back (i);

if(k>n) break;

}

if(length[n-1]==INT_MIN) cout<<":("<<endl;

else

if((x!=-1)&&((path.back()!=0)||(path.front()!=n-1)||(k>n))) cout<<":)"<<endl;

else cout<<length[n-1]<<endl;

return 0;

}

Засчитанное решение.

Код на ideone.

Создадим вектор расстояний length на n элементов. Все элементы кроме 0-го приравниваем к минимальному числу. Нулевой элемент приравниваем к 0. Также создадим вектор p в котором будем хранить номер вершины из которой мы попали в текущую. Затем в цикле проходим по всем вершинам и в вектор length записываем расстояние за которое мы дошли в эту вершину. n-1 элемент вектора и будет ответом задачи. Затем мы восстанавливаем путь из нулевой вершины в последнюю, но будем это делать не более n раз. Затем проверяем, если в последней вершине значение не изменилось то выводим :(. Затем проверяем был ли в пути цикл, если да то выводи :), в противном случае выводим значение length[n-1].

Related Images:

e-olymp 975

26/06/2015 by Сіренко Валерія Сергіївна

Задача:

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

Входные данные

В первой строке содержится количество вершин графа n (1 ≤ n ≤ 100). В следующих n строках находится по n чисел, которые задают матрицу смежности графа. В ней -1 означает отсутствие ребра между вершинами, а любое неотрицательное число — присутствие ребра данного веса. На главной диагонали матрицы всегда расположены нули.

Выходные данные

Вывести искомое максимальное кратчайшее расстояние.

#include <cstdlib>
#include <iostream>
 using namespace std;
 
int main(){
    int n;
    cin >> n;
    int a[n][n];
    long long maxr = 0;
    for( int i=0 ; i<n ; i++ ){
        for( int j=0 ; j<n ; j++ ){
            cin >> a[i][j];
        }
    }
    for( int k=0 ; k<n ; k++ ){
        for( int i=0 ; i<n ; i++ ){
            for( int j=0 ; j<n ; j++ ){
                if(i != j && a[i][k] != -1 && a[k][j] != -1){
                    if(a[i][j] == -1){
                        a[i][j] = a[i][k] + a[k][j];
                    }
                        else
                    {
                        a[i][j] = min(a[i][j], a[i][k] + a[k][j]);
                    }
                }
            }
        }
    }
    for( int i=0 ; i<n ; i++ )
    {
        for( int j=0 ; j<n ; j++ )
        {
            if(a[i][j] > maxr) maxr = a[i][j];
        }
    }
    cout << maxr << endl;
}

#include <cstdlib>

#include <iostream>

using namespace std;

int main(){

int n;

cin >> n;

int a[n][n];

long long maxr = 0;

for( int i=0 ; i<n ; i++ ){

for( int j=0 ; j<n ; j++ ){

cin >> a[i][j];

}

for( int k=0 ; k<n ; k++ ){

for( int i=0 ; i<n ; i++ ){

for( int j=0 ; j<n ; j++ ){

if(i != j && a[i][k] != -1 && a[k][j] != -1){

if(a[i][j] == -1){

a[i][j] = a[i][k] + a[k][j];

}

else

{

a[i][j] = min(a[i][j], a[i][k] + a[k][j]);

}

for( int i=0 ; i<n ; i++ )

{

for( int j=0 ; j<n ; j++ )

{

if(a[i][j] > maxr) maxr = a[i][j];

}

cout << maxr << endl;

}

Задача на e-olimp

Тесты

input	output
4 0 5 9 -1 -1 0 2 8 -1 -1 0 7 4 -1 -1 0	16
5 0 5 5 6 -1 -1 0 9 8 4 -1 -1 0 3 8 6 -1 -1 0 5 -1 2 5 6 0	14

Решение:

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