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

03/01/2019 by Кирилл Бондаренко

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

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

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

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

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

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

Тесты

ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
3 0 1 1 1 0 1 1 1 0	YES
3 0 1 0 1 0 1 1 1 0	NO
3 0 1 0 1 1 1 0 1 0	NO
4 0 1 0 0 1 0 1 1 1 1 0 1 0 1 1 1	NO

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

import java.util.*;
import java.lang.*;
import java.io.*;
import java.util.Scanner;
class Main {
	public static void main (String[] args) throws java.lang.Exception {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int k = n*n;
		int [] G = new int [k];
		for (int i = 0; i < G.length; i++) {
			G[i] = in.nextInt();
		}
		int j = 0, c = 0, s = 0;
		boolean f = true;
		for (int i = 0; i < k; i++) {
			if (G[i] != G[j]) {
				f=false;
				break;
			}
			if (c == n - 1) {
				c = 0;
				s++;
				j = s;
			} else {
				j = j + n;
				c++;
			}
		}
		for (int i = 0; i < k; i = i + n + 1) {
			if (G[i] != 0) {
				f = false;
				break;
			}
		}
		if (f) System.out.print("YES"); else System.out.print("NO");
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

import java.util.Scanner;

class Main {

public static void main (String[] args) throws java.lang.Exception {

Scanner in = new Scanner(System.in);

int n = in.nextInt();

int k = n*n;

int [] G = new int [k];

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

G[i] = in.nextInt();

}

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

boolean f = true;

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

if (G[i] != G[j]) {

f=false;

break;

}

if (c == n - 1) {

c = 0;

s++;

j = s;

} else {

j = j + n;

c++;

}

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

if (G[i] != 0) {

f = false;

break;

}

if (f) System.out.print("YES"); else System.out.print("NO");

}

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

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

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

28/12/2018 by Артем Чернобровкин

Задача

Простой неориентированный граф задан матрицей смежности. Найдите степени всех вершин графа.

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

В первой строке задано количество вершин графа [latex]n (1 ≤ n ≤ 100)[/latex]. Затем идут [latex]n[/latex] строк по [latex]n[/latex] элементов в каждой — описание матрицы смежности.

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

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

Тесты

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

Код задачи

import java.util.*;
public class Main
{
  public static void main(String[] args)

  {
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    //массив, в котором содержатся степени вершин
    int deg[] = new int[n];
    //Чтение матрицы смежности
    //и если есть ребро, то увеличиваем степень на 1
    for(int i = 0; i < n; i++)
    {
    	for(int j = 0; j < n; j++)

		 {
			int value = in.nextInt();
			if (value == 1)
    		{
    			deg[i]++;
    		}
		 }
    }
    //вывод результата
    for(int i = 0; i < n; i++)
    {
      System.out.println(deg[i]);     
    }
  }
}

import java.util.*;

public class Main

{

public static void main(String[] args)

{

Scanner in = new Scanner(System.in);

int n = in.nextInt();

//массив, в котором содержатся степени вершин

int deg[] = new int[n];

//Чтение матрицы смежности

//и если есть ребро, то увеличиваем степень на 1

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

{

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

{

int value = in.nextInt();

if (value == 1)

{

deg[i]++;

}

//вывод результата

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

{

System.out.println(deg[i]);

}

Решение

В ячейке [latex]deg[i][/latex] будем подсчитывать степень вершины [latex]i[/latex], которая равна количеству единиц в i-ой строки матрицы смежности.
Для неориентированного графа степень вершины — это количество всех инцидентных ей ребер.
Граф [latex]G=(V,U)[/latex] может быть задан матрицей смежности. Это квадратная матрица размерности [latex]n\times n[/latex], где [latex]n=\left |V \right | [/latex]. Матрица смежности неориентированного графа симметрична. Элементы матрицы смежности определяются следующим образом.
1- если [latex]i[/latex]-тая и [latex]j[/latex]-тая вершины графа смежны
0- иначе
[latex] a_{ij}=\left\{\begin{matrix}
1\\
0
\end{matrix}\right.\\[/latex]

Ссылки

Задача на e-olymp

Код задачи на ideone

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

25/12/2018 by Саша Рябова

Условие

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

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

Входной файл содержит число $n (1 \leq n \leq 100)$ — число вершин в графе, и затем $n$ строк по $n$ чисел, каждое из которых равно $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

Код задачи

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String answer = "YES";
        short[][] graph = new short [n][n];
        for (int i = 0; i < n; i++) {
            for( int j = 0; j < n; j++) {
                graph[i][j] = sc.nextShort();
            }
        }
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if (graph[i][j] == 1){ 
                    for (int z = 0; z < n; z++){
                        if (graph[j][z] == 1 && graph[i][z] == 0) { 
                            answer = "NO";
                            break;
                        }   
                    }   
                }
            }
        }
    System.out.print(answer);
    }
}

import java.util.*;

public class Main {

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

int n = sc.nextInt();

String answer = "YES";

short[][] graph = new short [n][n];

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

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

graph[i][j] = sc.nextShort();

}

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

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

if (graph[i][j] == 1){

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

if (graph[j][z] == 1 && graph[i][z] == 0) {

answer = "NO";

break;

}

System.out.print(answer);

}

Решение

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

Ссылки

Условие задачи на e-olymp
Код решения на ideone.com

e-olymp 1388. Заправки

16/12/2017 by Эммануил Прокопов

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

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

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

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

Сначала идет количество городов n (1 ≤ n ≤ 100), затем идет n чисел, i-ое из которых задает стоимость бензина в i-ом городе (все числа целые из диапазона от 0 до 100). Затем идет количество дорог m в стране, далее идет описание самих дорог. Каждая дорога задается двумя числами — номерами городов, которые она соединяет. Все дороги двухсторонние (то есть по ним можно ездить как в одну, так и в другую сторону); между двумя городами всегда существует не более одной дороги; не существует дорог, ведущих из города в себя.

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

Выведите одно число — суммарную стоимость маршрута или -1, если добраться невозможно.

Тесты

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

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

import java.util.*;

class Main
{
	//Условная бесконечность
	public static final int INF = 1000000;
	
	public static void main (String[] args)
	{
		Scanner input = new Scanner(System.in);
		int n, m, curFrom, curTo;
		n = input.nextInt();
		
		int price[] = new int[n+1];     //Цены на бензин в i-ом городе
		int distance[] = new int[n+1];  //Минимальные затраты на то, чтобы обраться до i-го города
		boolean used[] = new boolean[n+1]; //Был ли рассмотрен этот город?
		Vector <Integer> graph[] = new Vector[n+1];
		for (int i = 1; i <= n; ++i) {
			price[i] = input.nextInt();
			distance[i] = INF;
			used[i] = false;
			graph[i] = new Vector();
		}
		//Заполнение списка смежности
		m = input.nextInt();
		for (int i = 0; i < m; ++i) {
			curFrom = input.nextInt();
			curTo = input.nextInt();
			graph[curFrom].add(curTo);
			graph[curTo].add(curFrom);
		}
		//Нахождение оптимальной стоимости маршрута. На каждой итерации цикла находим город,
		//стоимость маршрута из начального города к которому минимальна. Если оказывается,
		//что эта стоимость бесконечна, значит, искомого пути не существует.
		distance[1] = 0;
		for(int i = 0; i < n; ++i) {
			int curCity = -1; //Город, рассматривыемый в данной итерации
			for (int j = 1; j <= n; ++j)
				if (!used[j] && (curCity == -1 || distance[j] < distance[curCity])) curCity = j;
			if (distance[curCity] == INF) break;
			used[curCity] = true;
			//Релаксация стоимости маршрута для всех городов, в которые можно попасти из данного
			for(int j = 0; j < graph[curCity].size(); ++j) {
				int to = graph[curCity].elementAt(j); 
				distance[to] = Math.min(distance[to], distance[curCity] + price[curCity]);
			}
		}
		//Вывод ответа
		System.out.print(distance[n] == INF ? -1 : distance[n]);
	}
}

import java.util.*;

class Main

{

//Условная бесконечность

public static final int INF = 1000000;

public static void main (String[] args)

{

Scanner input = new Scanner(System.in);

int n, m, curFrom, curTo;

n = input.nextInt();

int price[] = new int[n+1]; //Цены на бензин в i-ом городе

int distance[] = new int[n+1]; //Минимальные затраты на то, чтобы обраться до i-го города

boolean used[] = new boolean[n+1]; //Был ли рассмотрен этот город?

Vector <Integer> graph[] = new Vector[n+1];

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

price[i] = input.nextInt();

distance[i] = INF;

used[i] = false;

graph[i] = new Vector();

}

//Заполнение списка смежности

m = input.nextInt();

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

curFrom = input.nextInt();

curTo = input.nextInt();

graph[curFrom].add(curTo);

graph[curTo].add(curFrom);

}

//Нахождение оптимальной стоимости маршрута. На каждой итерации цикла находим город,

//стоимость маршрута из начального города к которому минимальна. Если оказывается,

//что эта стоимость бесконечна, значит, искомого пути не существует.

distance[1] = 0;

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

int curCity = -1; //Город, рассматривыемый в данной итерации

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

if (!used[j] && (curCity == -1 || distance[j] < distance[curCity])) curCity = j;

if (distance[curCity] == INF) break;

used[curCity] = true;

//Релаксация стоимости маршрута для всех городов, в которые можно попасти из данного

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

int to = graph[curCity].elementAt(j);

distance[to] = Math.min(distance[to], distance[curCity] + price[curCity]);

}

//Вывод ответа

System.out.print(distance[n] == INF ? -1 : distance[n]);

}

Описание

Оптимальную стоимость маршрута будем находить по алгоритму Дейкстры. Цены на бензин в i-ом городе хранятся в массиве price. Минимальные стоимости маршрутов к каждому из городов хранятся в массиве distance, изначально все маршруты принимаем бесконечно дорогими. Кроме того, для хранения информации о том, был ли рассмотрен i-й город, используется массив used. Сам граф представляется в виде списка смежности. Для этого используется массив векторов <strong>graph</strong>. Если в итоге стоимость маршрута до целевого города осталась бесконечной, значит, пути к нему не существует, и выводится -1. Иначе выводится эта стоимость.

Код на ideone.com.

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

e-olymp 975. Флойд

04/07/2017 by Шостак Дмитрий

Задача

Постановка задачи на e-olymp.

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

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

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

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

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

Тесты

№	n	matrix	Результат
1	4	0 5 9 -1 -1 0 2 8 -1 -1 0 7 4 -1 -1 0	16
2	3	0 -1 2 2 0 -1 4 1 0	4
3	5	0 -1 -1 3 4 2 0 3 -1 4 -1 4 0 -1 4 3 -1 2 0 1 1 1 -1 -1 0	8

Ссылка на успешно пройденные тесты на сайте e-olymp.

Решение

import java.util.*;
public class Graph {

    public static void main(String[] args){
        Scanner input =  new Scanner(System.in);

        int n, max = 0;
        n = input.nextInt();
        int[][] matrix = new int[n][n];

        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                matrix[i][j] = input.nextInt();
            }
        }

        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                for(int k = 0; k < n; k++){
                    if(j != k && matrix[j][i] != -1 && matrix[i][k] != -1){
                        if(matrix[j][k] == -1)
                            matrix[j][k] = matrix[j][i] + matrix[i][k];
                        else
                            matrix[j][k] = Math.min(matrix[j][k], matrix[j][i] + matrix[i][k]);
                    }
                }
            }
        }

        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(matrix[i][j] > max) max = matrix[i][j];
            }
        }

        System.out.println(max);
    }
}

import java.util.*;

public class Graph {

public static void main(String[] args){

Scanner input = new Scanner(System.in);

int n, max = 0;

n = input.nextInt();

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

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

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

matrix[i][j] = input.nextInt();

}

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

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

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

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

if(matrix[j][k] == -1)

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

else

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

}

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

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

if(matrix[i][j] > max) max = matrix[i][j];

}

System.out.println(max);

}

Проверить работу кода можно в облаке по ссылке — Ideone.

Пояснения

Данная задача решается при использовании алгоритма Флойда-Уоршелла, суть которого состоит в нахождении длин кратчайших путей между всеми парами вершин во взвешенном ориентированном графе. Код данного алгоритма можно наблюдать в цикле по [latex]i[/latex], в котором имеются два вложенных цикла по [latex]j[/latex] и по [latex]k[/latex]. Здесь мы проходим по элементам матрицы смежности графа, проверяя существует ли ребро между вершинами. Далее следуя алгоритму Флойда выполняем следующее действие — с помощью функции Math.min() находим минимальный путь из одной вершины в другую, записывая его в матрицу. По нахождении всех кратчайших путей, находим максимальный из них, и выводим его в консоль.

java@Cat

Учебные материалы по изучению основ языка програvмирования Java

Tag Archives: граф

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

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

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

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

Тесты

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

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

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

Задача

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

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

Тесты

Код задачи

Решение

Ссылки

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

Условие

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

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

Тесты

Код задачи

Решение

Ссылки

e-olymp 1388. Заправки

e-olymp 975. Флойд

Задача

Тесты

Решение

Пояснения