e-olimp 4650. Граф-Турнир

26.06.2017 by Алексей Маслеев

Задача на e-olimp

Оригинал решения

Тесты на Try Haxe!

Постановка задачи:

Построить на [latex]n[/latex] вершинах турнир, расстояние между любой парой вершин в котором не превышает двух рёбер.

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

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

Контур графа (рёбра вида [latex](k,k+1)[/latex]) ориентирован по часовой стрелке.
В дальнейших построениях будем отталкиваться от контура: каждая вершина графа должна находиться в хотя бы в одном цикле длины три с данной. Опишем процедуру построения такого орграфа: начиная с вершины под номером 1 будем просматривать все остальные вершины. Если на некотором шаге ребро, связывающее вершины, не ориентировано, то ориентируем его образом, противоположным ориентации ребра, соединяющего текущую вершину-исток и предыдущую по номеру вершину в обходе. Более конструктивно процедура формулируется так: обойти все вершины в порядке их следования в контуре. Пусть номер стартовой вершины для исходной итерации — [latex]V_i[/latex], рассматриваемой на данном шаге — [latex]V_k[/latex] Если ребро [latex](V_i,V_k)[/latex] не ориентировано, и номера обеих вершин (не)чётны — задать ориентацию [latex][V_i,V_k][/latex], иначе — [latex][V_k,V_i][/latex].

Исключение — граф [latex]K_4[/latex]: степень каждой вершины равна трём, следовательно, одно ребро каждой вершины не принадлежит контуру. Но таких рёбер всего два, следовательно, невозможно задать чередование ориентаций рёбер и получить четыре цикла длины 3. Для всех графов на большем числе вершин построение всегда возможно.

Реализация:

Для решения задачи достаточно хранить граф в форме матрицы смежности.

Тесты:

n = 5 \begin{pmatrix}0 & 1 & 1&0&0 \\0 & 0 & 1&1&0 \\0 & 0 &0&1&1\\1 & 0& 0&0&1\\1 & 1 & 0&0&0\end{pmatrix}
n = 3 \begin{pmatrix}0 & 1 & 0 \\0 & 0 & 1 \\1 & 0 & 0 \end{pmatrix}

Код:

class Test{
    static function main(){
        var n = Std.parseInt(Sys.stdin().readLine());
        var a:Array<Array<Int>> = [for (i in 0...n) [for (j in 0...n) 0]];        
		if (n == 4){
        	trace("-1");     
        }            
        for(i in 0...n){
        	a[i][(i+1)%n] = 1;  
        }    	
    	for(i in 0...n){
         	for(j in 0...n){
                if((a[i][j] + a[j][i] == 0) && (i != j)){
                    if(i % 2 == j % 2){
                        a[i][j] = 1;
                    }
                    else a[j][i] = 1;                    
                }
            }
        }
		for(i in 0...n){
        	for(j in 0...n){
                trace(a[j][i]);
            }
            trace(" ");
        }
    }
}

class Test{

static function main(){

var n = Std.parseInt(Sys.stdin().readLine());

var a:Array<Array<Int>> = [for (i in 0...n) [for (j in 0...n) 0]];

if (n == 4){

trace("-1");

}

for(i in 0...n){

a[i][(i+1)%n] = 1;

}

for(i in 0...n){

for(j in 0...n){

if((a[i][j] + a[j][i] == 0) && (i != j)){

if(i % 2 == j % 2){

a[i][j] = 1;

}

else a[j][i] = 1;

}

for(i in 0...n){

for(j in 0...n){

trace(a[j][i]);

}

trace(" ");

}

e-olymp 4853. Кратчайший путь

14.06.2017 by Маша Лукьянова

Задача взята из e-olimp

Условие:

Задан неориентированный граф. Найдите кратчайший путь от вершины $start$ до вершины $end$.

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

В первой строке находится два целых числа $n$ и $m$ $ (1 ≤ n ≤ 50000, 1 ≤ m ≤ 100000)$ — количества вершин и рёбер соответственно. Во второй строке заданы целые числа $start$ и $end$ — стартовая и конечная вершина соответственно. Далее идут $m$ строк, описывающие рёбра.

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

Если пути между $start$ и $end$ нет, то выведите $-1$. Иначе выведите в первой строке длину $l$ кратчайшего пути между этими двумя вершинами в рёбрах, а во второй строке выведите $l + 1$ число — вершины этого пути.

Тесты:

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

Решение:

Поскольку нам необходимо найти кратчайшее расстояние между вершинами реализуем поиском в ширину. Запомним посещенные вершины в массиве [latex]used[/latex], родительские вершины в массиве [latex]parent[/latex], а план посещений в списке [latex]plan[/latex].

Изначально в списке [latex]plan[/latex] находится единственная вершина $start$. Каждый шаг начинается с того, что мы берем первую вершину из списка [latex]plan[/latex], отмечаем ее как посещенную, удаляем из списка и после посещаем все ее соседние вершины, которые еще не были посещены.

Когда очередь опустеет, обход в ширину обойдёт все достижимые из [latex]point[/latex] вершины, причём до каждой дойдёт кратчайшим путём. После того, как кратчайший путь найден — мы с помощью массива «предков» восстанавливаем его.

import cpp.vm.Gc;
import cpp.Lib;
import sys.io.*;

class Main {
	
    static function main() {
		var n = 5;
		var m = 4;
		
		var g = new Array < Array<Int> >(); 	//граф
		
		var taskIn = new Array < Array<Int> >();	//ввод
		
		for (i in 0...n){
			g[i] = new Array <Int>();
		}
		
		var start = 1; //начальная вершина
		var end = 4; //конечная вершина
		
		--start;
		--end;
		
		taskIn.push([2, 3]); //вводимые ребра
		taskIn.push([1, 2]);
		taskIn.push([3, 5]);
		taskIn.push([3, 4]);
		taskIn.push([4, 3]);
		
		
		
		for (x in taskIn){
			var v1 = --x[0]; // декремент -> нумерация с 0
			var v2 = --x[1];

			g[v1].push(v2);
			g[v2].push(v1);
			
		}
		
		var plan = new List<Int>();
		var used = new Array<Bool>();
		var parent = new Array<Int>();
		
		
		for (i in 0...n){
			used.push(false);
			parent.push(0);
		}
		
		
		plan.add(start);
		used [start] = true;
		parent [start] = start;
		
		var point : Int = start;

		//пока не достигли конца и пока план не пуст
		while (point != end && !plan.isEmpty()){  
			point = plan.first();
			plan.pop();
			
			for (x in g[point]){
				
				if (!used[x]){
					used[x] = true;
					plan.add(x);
					parent[x] = point;
				}
			}
		}
		

		var answ: String = "";	//ответ
		
		if (point == end){	//если достигли конца -> путь существует
			var path = new Array<Int>();
			
			while (point != start){
				path.push(point);
				point = parent[point];
			}
			
			path.push(start);
			path.reverse();
			
			trace (path.length - 1);
			for (x in path)
				answ += x + 1 + " ";
		}else{
			answ = -1 + "";
		}
		trace(answ);

		
    }
}

import cpp.vm.Gc;

import cpp.Lib;

import sys.io.*;

class Main {

static function main() {

var n = 5;

var m = 4;

var g = new Array < Array<Int> >(); //граф

var taskIn = new Array < Array<Int> >(); //ввод

for (i in 0...n){

g[i] = new Array <Int>();

}

var start = 1; //начальная вершина

var end = 4; //конечная вершина

--start;

--end;

taskIn.push([2, 3]); //вводимые ребра

taskIn.push([1, 2]);

taskIn.push([3, 5]);

taskIn.push([3, 4]);

taskIn.push([4, 3]);

for (x in taskIn){

var v1 = --x[0]; // декремент -> нумерация с 0

var v2 = --x[1];

g[v1].push(v2);

g[v2].push(v1);

}

var plan = new List<Int>();

var used = new Array<Bool>();

var parent = new Array<Int>();

for (i in 0...n){

used.push(false);

parent.push(0);

}

plan.add(start);

used [start] = true;

parent [start] = start;

var point : Int = start;

//пока не достигли конца и пока план не пуст

while (point != end && !plan.isEmpty()){

point = plan.first();

plan.pop();

for (x in g[point]){

if (!used[x]){

used[x] = true;

plan.add(x);

parent[x] = point;

}

var answ: String = ""; //ответ

if (point == end){ //если достигли конца -> путь существует

var path = new Array<Int>();

while (point != start){

path.push(point);

point = parent[point];

}

path.push(start);

path.reverse();

trace (path.length - 1);

for (x in path)

answ += x + 1 + " ";

}else{

answ = -1 + "";

}

trace(answ);

}

try online

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

13.06.2017 by Сергей Завада

Ссылка на оригинальную статью.

Условие:

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

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

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

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

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

Решение:

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

Тесты:

Input

Output

4
0 5 9 100
100 0 2 8
100 100 0 7
4 100 100 0

0 5 7 13

12 0 2 8

11 16 0 7

4 9 11 0

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

import neko.Lib;
/**
 * ...
 * @author Zavada Sergey
 */
class Main 
{
	static function main() 
	{
		var n:Int = Std.parseInt(Sys.stdin().readLine());
		var w:Array<Array<Float>> = [for (x in 0...n) [for (y in 0...n) 0]];
		for (i in 0...n)
		{
			for (j in 0...n)
			{
				w[i][j] = Std.parseFloat(Sys.stdin().readLine());
			}
		}
		for (k in 0...n)
		{
			for (i in 0...n)
			{
				for (j in 0...n)
				{
					w[i][j] = Math.min(w[i][j], w[i][k]+w[k][j]);
				}
			}
		}
		var output = Sys.stdout();
		for (i in 0...n)
		{
			for (y in 0...n)
			{
				output.writeString(Std.string(w[i][y]) + " ");
			}
			output.writeString("\n");
		}	
	}
}

import neko.Lib;

/**

* ...

* @author Zavada Sergey

class Main

{

static function main()

{

var n:Int = Std.parseInt(Sys.stdin().readLine());

var w:Array<Array<Float>> = [for (x in 0...n) [for (y in 0...n) 0]];

for (i in 0...n)

{

for (j in 0...n)

{

w[i][j] = Std.parseFloat(Sys.stdin().readLine());

}

for (k in 0...n)

{

for (i in 0...n)

{

for (j in 0...n)

{

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

}

var output = Sys.stdout();

for (i in 0...n)

{

for (y in 0...n)

{

output.writeString(Std.string(w[i][y]) + " ");

}

output.writeString("\n");

}

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

06.06.2017 by Николай Яковлев

Ссылка на оригинальную статью

Ссылка на Try Haxe!

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

В 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
4 4 0 1 10 1 2 20 2 3 30 3 0 -61	possible
3 3 0 1 -100 1 2 1 2 1 0	not possible

Код

class Main 
{
	static function main() 
	{
		var inf = 2000000;
		var n = getNextInt();
		var m = getNextInt();
		
		var canals:Array<Canal> = [for (i in 0...m) createNextCanal() ];
		var distance:Array<Int> = [for (i in 0...n) 0];
		
		var x:Int = 0;
		for (i in 0...n) 
		{
			x = -1;
			for (j in 0...m) 
			{
				if (distance[canals[j].get_y()] > distance[canals[j].get_x()] + canals[j].get_t())
				{
					distance[canals[j].y] = int(Math.max(-inf, distance[canals[j].get_x()] + canals[j].get_t()));
					x = canals[j].get_y();
				}
			}
		}
		
		var output = Sys.stdout();
		output.writeString((x == -1 ? "not possible" : "possible") + "\n");
	}
	
	static function createNextCanal() 
	{
		var x = getNextInt();
		var y = getNextInt();
		var t = getNextInt();
		
		return new Canal(x, y , t);
	}
	
	static function getNextInt()
	{
		var number = Sys.stdin().readLine();
		return Std.parseInt(number);
	}
}

class Canal
{
	@:isVar public var x(get, set):Int;
	@:isVar public var y(get, set):Int;
	@:isVar public var t(get, set):Int;
	
	public function get_x() return x;
	public function set_x(x) return this.x = x;
	
	public function get_y() return y;
	public function set_y(y) return this.y = y;
	
	public function get_t() return t;
	public function set_t(t) return this.t = t;
	
	public function new(x:Int, y:Int, t:Int) 
	{
		this.x = x;
		this.y = y;
		this.t = t;
	}
}

class Main

{

static function main()

{

var inf = 2000000;

var n = getNextInt();

var m = getNextInt();

var canals:Array<Canal> = [for (i in 0...m) createNextCanal() ];

var distance:Array<Int> = [for (i in 0...n) 0];

var x:Int = 0;

for (i in 0...n)

{

x = -1;

for (j in 0...m)

{

if (distance[canals[j].get_y()] > distance[canals[j].get_x()] + canals[j].get_t())

{

distance[canals[j].y] = int(Math.max(-inf, distance[canals[j].get_x()] + canals[j].get_t()));

x = canals[j].get_y();

}

var output = Sys.stdout();

output.writeString((x == -1 ? "not possible" : "possible") + "\n");

}

static function createNextCanal()

{

var x = getNextInt();

var y = getNextInt();

var t = getNextInt();

return new Canal(x, y , t);

}

static function getNextInt()

{

var number = Sys.stdin().readLine();

return Std.parseInt(number);

}

class Canal

{

@:isVar public var x(get, set):Int;

@:isVar public var y(get, set):Int;

@:isVar public var t(get, set):Int;

public function get_x() return x;

public function set_x(x) return this.x = x;

public function get_y() return y;

public function set_y(y) return this.y = y;

public function get_t() return t;

public function set_t(t) return this.t = t;

public function new(x:Int, y:Int, t:Int)

{

this.x = x;

this.y = y;

this.t = t;

}

Ход решения

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

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

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

e-olymp 4000. Обход в глубину

24.04.2017 by Маша Лукьянова

Задача взята из e-olimp

Условие:

Имя входного файла: «input.txt»

Имя выходного файла: стандартный поток вывода

Ограничение по времени: 1 second

Ограничение по памяти: 122.17 мегабайт

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

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

В первой строке содержится количество вершин графа [latex] n [/latex] и выделенная вершина [latex] s [/latex] [latex](1 ≤ s ≤ n ≤ 100) [/latex]. В следующих [latex] n [/latex] строках записано по [latex] n [/latex] чисел — матрица смежности графа, в которой цифра [latex] «0» [/latex] означает отсутствие ребра между вершинами, а цифра [latex] «1» [/latex] — его наличие. Гарантируется, что на главной диагонали матрицы всегда стоят нули.

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

Выведите искомое количество вершин.

Тесты:

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

Решение:

Поскольку нам необходимо найти компоненту связности, запустим из исходной вершины поиск в глубину, запоминая посещенные вершины в массиве [latex] used [/latex]. Те вершины, которые мы посетили — принадлежат той же компоненте связности, что и исходная вершина. Таким образом, подсчитав кол-во посещенных вершин, мы решим задачу.

package;

import cpp.Lib;
import sys.io.*;

class Main 
{
	
	static function main() 
	{
		var inp = File.read("input.txt", false);
		var d = inp.readLine();
		var dd = d.split(' ');
		
		var n = Std.parseInt(dd[0]);
		var s = Std.parseInt(dd[1]);
		s--;
			
		var graph = new Array<Array>();
		var used = new Array  ();
		
		function DFS(v : Int){
			if (used[v])
				return;
				
			used[v] = true;
			for (i in 0...(graph[v].length)){
				DFS (graph[v][i]);
			}
		}
			
		for (i in 0...n){
			graph[i] = new Array();
			used[i] = false;
		}
		
		for (i in 0...n){
			var arr = inp.readLine().split(' ');
			for (j in 0...n){
				if (arr[j] == "1")
					graph[i].push(j);
			}
		}  
		
		DFS(s);
		
		var count = 0;
		
		for (i in 0...n){
			if (used[i])
				count ++; 
		}
		
		Sys.stdout().writeString(count + "");
	}
}

package;

import cpp.Lib;

import sys.io.*;

class Main

{

static function main()

{

var inp = File.read("input.txt", false);

var d = inp.readLine();

var dd = d.split(' ');

var n = Std.parseInt(dd[0]);

var s = Std.parseInt(dd[1]);

s--;

var graph = new Array<Array>();

var used = new Array ();

function DFS(v : Int){

if (used[v])

return;

used[v] = true;

for (i in 0...(graph[v].length)){

DFS (graph[v][i]);

}

for (i in 0...n){

graph[i] = new Array();

used[i] = false;

}

for (i in 0...n){

var arr = inp.readLine().split(' ');

for (j in 0...n){

if (arr[j] == "1")

graph[i].push(j);

}

DFS(s);

var count = 0;

for (i in 0...n){

if (used[i])

count ++;

}

Sys.stdout().writeString(count + "");

}

Алексей Маслеев	Сергей Завада	Анастасия Улановская
Владислав Козачков	Николай Яковлев	Даша Тарабаева
Лена Наумова	Денис Швецов	Артур Тарасов
Евгений Кравчук	Дарья Пиндус	Артём Мисесин
Даша Кивганова	Иоанна Васильева	Алёна Ищук
Кирилл Автомонов	Александр Зайченко	Маша Лукьянова
Игорь Варламов	Геннадий Муржи

haxe

Учебные материалы по программированию

Category Archives: D. Графы

e-olimp 4650. Граф-Турнир

Постановка задачи:

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

Реализация:

Тесты:

Код:

e-olymp 4853. Кратчайший путь

Условие:

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

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

Тесты:

Решение:

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

Условие:

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

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

Решение:

Тесты:

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

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

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

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

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

Тесты

Код

Ход решения

e-olymp 4000. Обход в глубину

Условие:

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

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

Тесты:

Решение: