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 974. Флойд-1

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

974. Флойд-1

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

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

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

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

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

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

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

#include <cstdlib>
#include <iostream>

using namespace std;

int **a;

int main()
{
    int n;
    cin >> n;
    a = new int*[n];
    for( int i=0 ; i<n ; i++ )
    {
        a[i] = new int [n];
        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][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++ )
        {
            cout << a[i][j] << ( j+1 == n ? '\n' : ' ' );
        }
    }
}

#include <cstdlib>

#include <iostream>

using namespace std;

int **a;

int main()

{

int n;

cin >> n;

a = new int*[n];

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

{

a[i] = new int [n];

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][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++ )

{

cout << a[i][j] << ( j+1 == n ? '\n' : ' ' );

}

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

Related Images:

e-olymp 625. Расстояние между вершинами

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

Задача с сайта e-olimp № 625.

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

РАССТОЯНИЕ МЕЖДУ ВЕРШИНАМИ

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

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

Первая строка входного файла содержит натуральные числа N, M, S и F (N ≤ 5000, M ≤ 100000, 1 ≤ S, F ≤ N, S ≠ F) — количество вершин и ребер графа а также номера вершин, длину пути между которыми требуется найти.

Следующие M строк содержат по три натуральных числа b_i, e_i и w_i — номера концов i-ого ребра и его вес соответственно (1 ≤b_i, e_i ≤ N, 0 ≤ w_i ≤ 100000).

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

Первая строка должна содержать одно натуральное число — вес минимального пути между вершинами S и F. Во второй строке через пробел выведите вершины на кратчайшем пути из S в F в порядке обхода. Если путь из S в F не существует, выведите -1.

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

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

vector <int> marsh;

int main() {
 
	int n, m1;
	cin>>n>>m1;
	if(n<0 || m1<0){
		cout<<"-1";
		return 0;
	}
	int s,f;
	cin>>s>>f;
	if(n==0 || n==1 || s==0 || f==0){ 
		cout<<"-1"<<endl;
		return 0;
	}
	int max;
	int M[m1][3];
	for(int i=0; i<m1 ; i++){
		for(int j=0; j<3 ; j++){
			cin>>M[i][j];
			max=M[0][0];
			if(M[i][j]<0){ 
				m1=i;
				break;
			}
			if(M[i][j]<0 ){
				cout<<"-1";
				return 0;
			}
		}
	}
	for(int i=0; i<m1 ; i++){
		for(int j=0; j<2 ; j++){
			if(M[i][j]>max){ max=M[i][j];}
        }
    }
	n=max;
	int V=n;
	int h[n];  //массив вершин которые принадлежат минимальному пути от s до f
	int a[n];
	int b[n];
	int GR[V][V]; //V
	for(int i=0; i<n ; i++){
		for(int j=0; j<n ; j++){
			GR[i][j]=0;
		}
	}
	//преобразовываю считанные данные  в матрицу смежности между вершинами 
	for(int i=0; i<m1 ; i++){  
		for(int j=0; j<3 ; j++){
			a[i]=M[i][0];
			b[i]=M[i][1];
			GR[a[i]-1][b[i]-1]=M[i][2];
			GR[b[i]-1][a[i]-1]=M[i][2];
		}
	}
	int st=s-1;
	int count, index, i, u, m=st+1;
	long long distance[V];
	bool visited[V];
	for (i=0; i<V; i++){							
		distance[i]=LLONG_MAX; visited[i]=false;
	}
	distance[st]=0;

	long long min;
	
	for (count=0; count<V-1; count++){							
		min=LLONG_MAX;
		for (i=0; i<V; i++)
	        if (!visited[i] && distance[i]<=min){
				min=distance[i]; index=i;
			}
			u=index;
			visited[u]=true;
		for (i=0; i<V; i++){												//V
			if (!visited[i] && GR[u][i] && distance[u]!=LLONG_MAX 
				&& distance[u]+GR[u][i]<distance[i]){
                       distance[i]=distance[u]+GR[u][i];
				       h[i]=u;
			}
		}
	}
	//вывод расстояния
	if(n!=0 && n!=1){
		for (i=0; i<1; i++){
	        if(s>n || f>n ){
				cout<<"-1";
				break;
			}
			if(distance[f-1]==LLONG_MAX){
				cout<<"-1"<<endl;
				break;
			}
			if (distance[i]!=LLONG_MAX  ){
				cout<<distance[f-1]<<endl;
				// вывод маршрута	
				s--;
				f--;
				int c=f;
				while (c!=(s)) {
					marsh.push_back(c+1); 
					c=h[c];
				}
				marsh.push_back(s+1);
				cout << marsh[marsh.size()-1];
				for(int t = marsh.size()-2; t >=0; t--) 
                                        cout << " " << marsh[t];
				        cout << 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

#include <iostream>

#include <vector>

#include <set>

#include <utility>

#include <climits>

using namespace std;

vector <int> marsh;

int main() {

int n, m1;

cin>>n>>m1;

if(n<0 || m1<0){

cout<<"-1";

return 0;

}

int s,f;

cin>>s>>f;

if(n==0 || n==1 || s==0 || f==0){

cout<<"-1"<<endl;

return 0;

}

int max;

int M[m1][3];

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

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

cin>>M[i][j];

max=M[0][0];

if(M[i][j]<0){

m1=i;

break;

}

if(M[i][j]<0 ){

cout<<"-1";

return 0;

}

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

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

if(M[i][j]>max){ max=M[i][j];}

}

n=max;

int V=n;

int h[n]; //массив вершин которые принадлежат минимальному пути от s до f

int a[n];

int b[n];

int GR[V][V]; //V

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

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

GR[i][j]=0;

}

//преобразовываю считанные данные в матрицу смежности между вершинами

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

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

a[i]=M[i][0];

b[i]=M[i][1];

GR[a[i]-1][b[i]-1]=M[i][2];

GR[b[i]-1][a[i]-1]=M[i][2];

}

int st=s-1;

int count, index, i, u, m=st+1;

long long distance[V];

bool visited[V];

for (i=0; i<V; i++){

distance[i]=LLONG_MAX; visited[i]=false;

}

distance[st]=0;

long long min;

for (count=0; count<V-1; count++){

min=LLONG_MAX;

for (i=0; i<V; i++)

if (!visited[i] && distance[i]<=min){

min=distance[i]; index=i;

}

u=index;

visited[u]=true;

for (i=0; i<V; i++){ //V

if (!visited[i] && GR[u][i] && distance[u]!=LLONG_MAX

&& distance[u]+GR[u][i]<distance[i]){

distance[i]=distance[u]+GR[u][i];

h[i]=u;

}

//вывод расстояния

if(n!=0 && n!=1){

for (i=0; i<1; i++){

if(s>n || f>n ){

cout<<"-1";

break;

}

if(distance[f-1]==LLONG_MAX){

cout<<"-1"<<endl;

break;

}

if (distance[i]!=LLONG_MAX ){

cout<<distance[f-1]<<endl;

// вывод маршрута

s--;

f--;

int c=f;

while (c!=(s)) {

marsh.push_back(c+1);

c=h[c];

}

marsh.push_back(s+1);

cout << marsh[marsh.size()-1];

for(int t = marsh.size()-2; t >=0; t--)

cout << " " << marsh[t];

cout << endl;

}

return 0;

}

После считывания входных данных создаем три массива. Массив вершин входящих в кратчайший путь, а также два массива для преобразования считанной матрицы в матрицу смежности вершин графа. Далее с помощью алгоритма Дейкстра находим кратчайшее расстояние до каждой вершины и одновременно записываем в массив [latex]h\left [ n \right ][/latex] вершины, через которые проходит кратчайший путь. Затем выводим расстояние до вершины [latex]f[/latex] если путь к ней существует, иначе печатаем: «-1». Далее выводим кратчайший маршрут между вершинами [latex]s[/latex] и [latex]f[/latex].

Related Images:

e-olymp 4850. Шайтан-машинка

17/06/2015 by Марченко Філіп Олександрович

Условие

У Ибрагима есть магическая чёрная шайтан-машинка. На ней есть три кнопки и табло. Табло может показывать не более чем четырёхзначные числа. Каждая из кнопок меняет число некоторым образом: первая домножает его на [latex]3[/latex], вторая прибавляет к нему сумму его цифр, а третья вычитает из него [latex]2[/latex]. В случае, если число становится отрицательным или превосходит [latex]9999[/latex], шайтан-машинка ломается.

Ибрагим может нажимать кнопки в любом порядке. Его интересует, как ему получить на табло число [latex]b[/latex] после некоторой последовательности нажатий, если сейчас шайтан-машинка показывает [latex]a[/latex]. Помогите ему найти минимальное необходимое число нажатий.

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

В одной строке находится два натуральных числа [latex]a[/latex] и [latex]b[/latex] latex[/latex].

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

Вывести минимальное необходимое количество действий.

Задача
Зачтённое решение

Код

Ideone

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <iostream>

using namespace std;

int sum_n (int n){ //подсчёт суммы цифер в числе
    int res = n/1000 + (n%1000-n%100)/100 + (n%100-n%10)/10 + n%10;
    return res;
}

bool was [10000]; //массив использованных вершин.
int vertex[10000]; //подсчёт кол-ва пройденных рёбер..
queue<int> q; //очередь для BFS

//BFS
void bfs (int start, int finish){
    if (start==finish){  //если мы сразу попали в нужную вершину - выходим из программы.
        cout << 0 << endl;
        return;
    }
    else {
        for (int i=0; i<10000; i++){ //предположим, что расстояние до любой вершины = 1
            vertex[i]=1;
        }
        q.push (start); //будем рассматривать каждую вершину
        was[start] = true;
        while (!q.empty()){
            int tmp = q.front(); //рассматриваемая вершина
            q.pop();
            int tmp1 = tmp;
            tmp1 *= 3; //"ребёнок" рассматриваемой вершины, со значением родителбской вершины *3.
            if (!was[tmp1]){
                if (tmp1 == finish){//если финиш, то выводим длину пути до вершины.
                    cout << vertex[tmp] << endl;
                    return;
                }
                else if (tmp1 < 10000 && tmp1>=0){
                    was[tmp1] = true;//иначе помечаем вершину, как пройденную и засовываем её в очередь на рассмотрение
                    q.push(tmp1);
                    vertex[tmp1]=vertex[tmp]+1;//и прибавляем 1 к длине пути.
                }
            }
            //действия повторяются для других операций.
            tmp1=tmp;
            tmp1 += sum_n(tmp1);
            if (!was[tmp1]){
                if (tmp1 == finish){
                    cout << vertex[tmp] << endl;
                    return;
                }
                else if (tmp1 < 10000 && tmp1>=0){
                    was[tmp1] = true;
                    vertex[tmp1]=vertex[tmp]+1;
                    q.push(tmp1);
                }
            }
            tmp1=tmp;
            tmp1 -= 2;
            if (!was[tmp1]){
                if (tmp1 == finish){
                    cout << vertex[tmp] << endl;
                    return;
                }
                else if (tmp1 < 10000 && tmp1>=0){
                    was[tmp1] = true;
                    vertex[tmp1]=vertex[tmp]+1;
                    q.push(tmp1);
                }
            }
        }
    }
}

int main() {
    int a, b;
    cin >> a >> b; //ввод начала и конца
    bfs (a, b);//процедура выполнения
    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <iostream>

using namespace std;

int sum_n (int n){ //подсчёт суммы цифер в числе

int res = n/1000 + (n%1000-n%100)/100 + (n%100-n%10)/10 + n%10;

return res;

}

bool was [10000]; //массив использованных вершин.

int vertex[10000]; //подсчёт кол-ва пройденных рёбер..

queue<int> q; //очередь для BFS

//BFS

void bfs (int start, int finish){

if (start==finish){ //если мы сразу попали в нужную вершину - выходим из программы.

cout << 0 << endl;

return;

}

else {

for (int i=0; i<10000; i++){ //предположим, что расстояние до любой вершины = 1

vertex[i]=1;

}

q.push (start); //будем рассматривать каждую вершину

was[start] = true;

while (!q.empty()){

int tmp = q.front(); //рассматриваемая вершина

q.pop();

int tmp1 = tmp;

tmp1 *= 3; //"ребёнок" рассматриваемой вершины, со значением родителбской вершины *3.

if (!was[tmp1]){

if (tmp1 == finish){//если финиш, то выводим длину пути до вершины.

cout << vertex[tmp] << endl;

return;

}

else if (tmp1 < 10000 && tmp1>=0){

was[tmp1] = true;//иначе помечаем вершину, как пройденную и засовываем её в очередь на рассмотрение

q.push(tmp1);

vertex[tmp1]=vertex[tmp]+1;//и прибавляем 1 к длине пути.

}

//действия повторяются для других операций.

tmp1=tmp;

tmp1 += sum_n(tmp1);

if (!was[tmp1]){

if (tmp1 == finish){

cout << vertex[tmp] << endl;

return;

}

else if (tmp1 < 10000 && tmp1>=0){

was[tmp1] = true;

vertex[tmp1]=vertex[tmp]+1;

q.push(tmp1);

}

tmp1=tmp;

tmp1 -= 2;

if (!was[tmp1]){

if (tmp1 == finish){

cout << vertex[tmp] << endl;

return;

}

else if (tmp1 < 10000 && tmp1>=0){

was[tmp1] = true;

vertex[tmp1]=vertex[tmp]+1;

q.push(tmp1);

}

int main() {

int a, b;

cin >> a >> b; //ввод начала и конца

bfs (a, b);//процедура выполнения

return 0;

}

Код на Java:

import java.util.*;
import java.lang.*;
import java.io.*;

class ShaitanEngines {
    private static int N = 10001;
    private static boolean [] was = new boolean [N];
    private static int [] vertice = new int [N];
    private static Queue <Integer> q = new LinkedList();
    public static int sum (int n) {
        return (n/1000 + (n%1000-n%100)/100 + (n%100-n%10)/10 + n%10);  
    }
    public static void bfs (int start, int finish) {
        if (start == finish) {
            System.out.println(1);
            return;
        }
        else {
            for (int i=0; i<N; i++){ //предположим, что расстояние до любой вершины = 1
                vertice[i]=1;
            }
            q.add (start); //будем рассматривать каждую вершину
            was[start] = true;
            while (!q.isEmpty()){
                int tmp = q.element(); //рассматриваемая вершина
                q.remove();
                int tmp1 = tmp;
                tmp1 *= 3; //"ребёнок" рассматриваемой вершины, со значением родителбской вершины *3.
                if (!was[tmp1]){
                    if (tmp1 == finish){//если финиш, то выводим длину пути до вершины.
                        System.out.println(vertice[tmp]);
                        return;
                    }
                    else if (tmp1 < 10000 && tmp1>=0){
                        was[tmp1] = true;//иначе помечаем вершину, как пройденную и засовываем её в очередь на рассмотрение
                        q.add(tmp1);
                        vertice[tmp1]=vertice[tmp]+1;//и прибавляем 1 к длине пути.
                    }
                }
                //действия повторяются для других операций.
                tmp1=tmp;
                tmp1 += sum(tmp1);
                if (!was[tmp1]){
                    if (tmp1 == finish){
                        System.out.println(vertice[tmp]);
                        return;
                    }
                    else if (tmp1 < 10000 && tmp1>=0){
                        was[tmp1] = true;
                        vertice[tmp1]=vertice[tmp]+1;
                        q.add(tmp1);
                    }
                }
                tmp1=tmp;
                tmp1 -= 2;
                if (!was[tmp1]){
                    if (tmp1 == finish){
                        System.out.println(vertice[tmp]);
                        return;
                    }
                    else if (tmp1 < 10000 && tmp1>=0){
                        was[tmp1] = true;
                        vertice[tmp1]=vertice[tmp]+1;
                        q.add(tmp1);
                    }
                }
            }
        }
    }
    public static void main (String[] args) {
        Scanner sc = new Scanner (System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        bfs(a, b);
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class ShaitanEngines {

private static int N = 10001;

private static boolean [] was = new boolean [N];

private static int [] vertice = new int [N];

private static Queue <Integer> q = new LinkedList();

public static int sum (int n) {

return (n/1000 + (n%1000-n%100)/100 + (n%100-n%10)/10 + n%10);

}

public static void bfs (int start, int finish) {

if (start == finish) {

System.out.println(1);

return;

}

else {

for (int i=0; i<N; i++){ //предположим, что расстояние до любой вершины = 1

vertice[i]=1;

}

q.add (start); //будем рассматривать каждую вершину

was[start] = true;

while (!q.isEmpty()){

int tmp = q.element(); //рассматриваемая вершина

q.remove();

int tmp1 = tmp;

tmp1 *= 3; //"ребёнок" рассматриваемой вершины, со значением родителбской вершины *3.

if (!was[tmp1]){

if (tmp1 == finish){//если финиш, то выводим длину пути до вершины.

System.out.println(vertice[tmp]);

return;

}

else if (tmp1 < 10000 && tmp1>=0){

was[tmp1] = true;//иначе помечаем вершину, как пройденную и засовываем её в очередь на рассмотрение

q.add(tmp1);

vertice[tmp1]=vertice[tmp]+1;//и прибавляем 1 к длине пути.

}

//действия повторяются для других операций.

tmp1=tmp;

tmp1 += sum(tmp1);

if (!was[tmp1]){

if (tmp1 == finish){

System.out.println(vertice[tmp]);

return;

}

else if (tmp1 < 10000 && tmp1>=0){

was[tmp1] = true;

vertice[tmp1]=vertice[tmp]+1;

q.add(tmp1);

}

tmp1=tmp;

tmp1 -= 2;

if (!was[tmp1]){

if (tmp1 == finish){

System.out.println(vertice[tmp]);

return;

}

else if (tmp1 < 10000 && tmp1>=0){

was[tmp1] = true;

vertice[tmp1]=vertice[tmp]+1;

q.add(tmp1);

}

public static void main (String[] args) {

Scanner sc = new Scanner (System.in);

int a = sc.nextInt();

int b = sc.nextInt();

bfs(a, b);

}

Решение

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

Всю «карту» расположения операций можно представить в виде графа-дерева, где от каждой вершины отходят максимум 3 ребра (в каждой вершине по операции, проделанной со значением вершины, которая находится на уровень выше). Будем рассматривать каждую вершину. Если исходная вершина и есть конечной, то выходим из программы с вердиктом «0». Иначе будем поочерёдно рассматривать все вершины. Заведём массив расстояний, в котором предположим, что расстояние до нужной нам вершины равно 1. С проходом каждой вершины будем подсчитывать расстояние до нужной нам вершины (прибавляя к расстоянию 1), в которую мы рано или поздно попадём.

Related Images:

e-olymp 5073. Проверка на наличие параллельных ребер (ОГ)

16/06/2015 by Байков Дмитро

Ориентированный граф задан списком ребер.

Проверьте, содержит ли он параллельные ребра.

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

Входной файл содержит числа [latex]n(1\leq n\leq 100)[/latex] — число вершин в графе и [latex]m(1\leq m\leq 10000)[/latex] — число ребер. Затем следует [latex]m[/latex] пар чисел — ребра графа.

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

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

Задача на e-olimp. Ссылка на засчитанное решение.

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

Код задачи:

#include <iostream>
using namespace std;

int main() 
{
	int n, m, i = 0, k = 0;
	bool p = true;
	cin >> n >> m;
	int v[m], g[m];
	for (int i = 0; i < m; i ++)
	{
		cin >> v[i] >> g[i];
	}
	while (p)
	{
		for (int j = i+1; j < m; j ++)
		{
			if ( (v[i] == v[j]) && (g[i] == g[j]) ) 
			{ 
				k++; 
				cout<<"YES"<<endl; 
				p=false; //Выход из цикла.
			}
		}
		i ++;
		if (i == m) break; //Условие окончания цикла.
	}
	if (k == 0) cout<<"NO"<<endl;
	return 0;
}

#include <iostream>

using namespace std;

int main()

{

int n, m, i = 0, k = 0;

bool p = true;

cin >> n >> m;

int v[m], g[m];

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

{

cin >> v[i] >> g[i];

}

while (p)

{

for (int j = i+1; j < m; j ++)

{

if ( (v[i] == v[j]) && (g[i] == g[j]) )

{

k++;

cout<<"YES"<<endl;

p=false; //Выход из цикла.

}

i ++;

if (i == m) break; //Условие окончания цикла.

}

if (k == 0) cout<<"NO"<<endl;

return 0;

}

Ссылка на ideone.

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

Сначала, добавим пару вершин в разные массивы так, чтоб нулевой элемент массива [latex]v[i][/latex] был началом ребра, а нулевой элемент массива [latex]g[i][/latex] — концом ребра и т.д. После этого в цикле будем сравнивать поочередно пары вершин до тех пор, пока не узнаем, что такая пара вершин уже встречалась, в таком случае выводим YES и завершаем цикл. В противном случае, если наше условие не выполнилось ни разу (т.е. переменная [latex]k[/latex] как была нулем в начале программы, так и осталась) выводим NO.

Код на Java

import java.util.*;
import java.lang.*;
import java.io.*;

class Graph
{
	public static void main (String[] args) throws java.lang.Exception
	{
		int ii = 0, k = 0;
		Boolean p = true;
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int m = in.nextInt();
		int[] v = new int[m], g = new int[m];
		for (int i = 0; i < m; i ++)
		{
			v[i] = in.nextInt();
			g[i] = in.nextInt();
		}
		while (p)
		{
			for (int j = ii+1; j < m; j ++)
			{
				if ((v[ii] == v[j]) && (g[ii] == g[j])) 
				{ 
					k++; 
					System.out.println("YES"); 
					p=false; //Выход из цикла.
				}
			}
			ii ++;
			if (ii == m) break; //Условие окончания цикла.
		}
		if (k == 0) System.out.println("NO"); 
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Graph

{

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

{

int ii = 0, k = 0;

Boolean p = true;

Scanner in = new Scanner(System.in);

int n = in.nextInt();

int m = in.nextInt();

int[] v = new int[m], g = new int[m];

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

{

v[i] = in.nextInt();

g[i] = in.nextInt();

}

while (p)

{

for (int j = ii+1; j < m; j ++)

{

if ((v[ii] == v[j]) && (g[ii] == g[j]))

{

k++;

System.out.println("YES");

p=false; //Выход из цикла.

}

ii ++;

if (ii == m) break; //Условие окончания цикла.

}

if (k == 0) System.out.println("NO");

}

Related Images:

e-olymp 5072. Подсчет количества ребер (ОГ)

28/05/2015 by Царев Николай Александрович

Задача

Ориентированный граф задан матрицей смежности.
Найдите количество ребер в графе.

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

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

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

Выведите в выходной файл количество ребер заданного графа.

Решение

Задача на E-Olimp.

30 1 11 0 1

0 1 1

50 1 1 1 11 0 0 0 0

1 0 0 0 0

0 0 1 0 1

1 0 0 0 0

21 11 1

#include <iostream>

using namespace std;

int main()
{
    int n;
    cin >> n;
    int k, l=0;
    for(int i=0;i<n;i++){
        for(int j=0; j<n; j++){
            cin >> k;
            if(k)
            l++;
        }
    }
    cout << l << endl;

    return 0;
}

#include <iostream>

using namespace std;

int main()

{

int n;

cin >> n;

int k, l=0;

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

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

cin >> k;

if(k)

l++;

}

cout << l << endl;

return 0;

}

Алгоритм решения прост. Количество ребер ориентированного графа равно количеству единиц в его матрице смежности. Поэтому просто считываем, суммируем если 1, и выводим ответ.

Задача на ideone

Related Images:

e-olymp 976. Флойд — существование

14/05/2015 by Осецимський Анатолій Вадимович

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

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

Пройденный тесты.

e-olymp 976. Флойд — существование

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

Кратчайший путь может не существовать по двум причинам:

Нет ни одного пути.
Есть путь сколь угодно маленького веса

Пройденный тесты.

Первая задача решается Алгоритмом Флойда-Уоршела. Поскольку отрицательных ребер в графе нет, и просят вывести кратчайший путь к каждой из вершин, то надо было всего лишь определить, что мы возьмем за бесконечность. Я выбрал [latex]10001[/latex], поскольку максимальное количество вершин [latex]100[/latex], а вес ребер не превышает [latex]100[/latex], соответственной максимально возможное расстояние не превосходит [latex]100*100 = 10000[/latex].

Во второй задаче была та же идея, но в данной ситуация у нас были ребра отрицательного веса. И у нас появилась проблема, могли существовать циклы отрицательной длины(с каждым проходом расстояние до вершин уменьшалось). Поскольку мы пользовались [latex]while[/latex] -ом, мы зацикливались. По этому необходимо было прекращать добавлять вершины, которую имеют отрицательную индексацию и порогом выбрано [latex]-102[/latex], поскольку цикл мог содержать отрицательные ребра, но при это быть положительным, по этому [latex]<0[/latex] нам не подошло. Дальше необходимо было вывести матрицу существования, методом [latex]way[/latex] мы выходили из вершины и определяли индексацию, пуская из всех вершин, мы можем построково выводить матрицу, только необходимо восстанавливать к исходному виду сам граф. В выводе мы определяли, существует путь и мал ли он. Существование проверялось тем, что эта вершина была посещена, а путь к вершине проверялся по индексу, если он меньше половины порога остановки[latex](-50)[/latex], то путь к этой вершине бесконечен.

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

struct vertax{ // структура вершина
	int vert, index, father; bool visited;
	vertax(int a){vert = a; index = 10001; father = a;visited = false;}
	vertax(int a, int b){
		vert = a;
		father = b;
		index = 10001;visited = false;
	}
	vertax(int a, int b, int x){
		vert = a;
		father = b;
		index = x;visited = false;
	}
	vector<vertax> follow;// с кем связанна эта вершина
	~vertax(){}
};

struct graph{
	vector<vertax> v; // list of vertax
	int count;
	graph(){};
	graph(int n){
		count = n;
	}
	void get(){//инициализируем граф
		for(int i = 1; i <= count; i++){
			vertax v(i);
			for(int j = 1; j <= count; j++){
				int x;
				cin >> x;
				if(x != 0){
					vertax temp(j, i, x);
					v.follow.push_back(temp);
				}
			}
			graph::v.push_back(v);
		}
	}
	void write(){//вывод вершины, и с кем она связанна
		for(int i = 0; i < count; i++){
			cout << v[i].index << ":";
			for(int j = 0; j < v[i].follow.size(); j++){
				cout << v[i].follow[j].vert << " ";
			}
			cout << endl;
		}
	}
	void way(vertax& x){//алгоритм
		deque<vertax> list;
		x.index = 0;
		x.visited = true;
		list.push_front(x);
		while(!list.empty()){
			vertax& y = list[0];
			for(int i = 0; i < y.follow.size();i++){
				v[y.follow[i].vert -1].visited = true;
				if(v[y.follow[i].vert-1].index > y.index+y.follow[i].index){
					v[y.follow[i].vert-1].index = y.index+y.follow[i].index;
					if(v[y.follow[i].vert-1].index > -102){
						list.push_back(v[y.follow[i].vert-1]);
					}
				}
			}
			list.pop_front();
		}
	}
	void def(){//фунция к приведению значений по умолчанию
		for(int i = 0; i < v.size(); i++){
			v[i].index = 10001;
			v[i].visited = false;
		}
	}
	void task1(){ // Решение задачи e-olymp.com №976: Флойд - существование
		for(int i = 0; i < v.size(); i++){
			way(v[i]);
			for(int j = 0; j < v.size()-1; j++){
				if(!v[j].visited){
					cout << 0 << " ";
				}else if(v[j].index < -50){
					cout << 2 << " ";
				}else{
					cout << 1 << " ";
				}
			}
			if(!v[v.size()-1].visited){
					cout << 0 ;
				}else if(v[v.size()-1].index < -50){
					cout << 2 ;
				}else{
					cout << 1 ;
				}
			def();
			cout << endl;
		}
	}
	void task2(){ // Решение задачи e-olymp.com №974: Флойд-1
		for(int i = 0; i < v.size(); i++){
			way(v[i]);
			for(int j = 0; j < v.size()-1; j++){
				if(!v[j].visited){
					cout << 0 << " ";
				}else{
					cout << v[j].index << " ";
				}
			}
			if(!v[v.size()-1].visited){
					cout << 0 ;
				}else{
					cout << v[v.size()-1].index;
				}
			def();
			cout << endl;
		}
	}
};


int main() {
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	graph dog(n);
	dog.get();
	dog.task1();// Решаем задачу №976: Флойд - существование
	dog.task2();// Решаем задачу №974: Флойд-1
	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

#include <iostream>

#include <vector>

#include <deque>

using namespace std;

struct vertax{ // структура вершина

int vert, index, father; bool visited;

vertax(int a){vert = a; index = 10001; father = a;visited = false;}

vertax(int a, int b){

vert = a;

father = b;

index = 10001;visited = false;

}

vertax(int a, int b, int x){

vert = a;

father = b;

index = x;visited = false;

}

vector<vertax> follow;// с кем связанна эта вершина

~vertax(){}

};

struct graph{

vector<vertax> v; // list of vertax

int count;

graph(){};

graph(int n){

count = n;

}

void get(){//инициализируем граф

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

vertax v(i);

for(int j = 1; j <= count; j++){

int x;

cin >> x;

if(x != 0){

vertax temp(j, i, x);

v.follow.push_back(temp);

}

graph::v.push_back(v);

}

void write(){//вывод вершины, и с кем она связанна

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

cout << v[i].index << ":";

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

cout << v[i].follow[j].vert << " ";

}

cout << endl;

}

void way(vertax& x){//алгоритм

deque<vertax> list;

x.index = 0;

x.visited = true;

list.push_front(x);

while(!list.empty()){

vertax& y = list[0];

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

v[y.follow[i].vert -1].visited = true;

if(v[y.follow[i].vert-1].index > y.index+y.follow[i].index){

v[y.follow[i].vert-1].index = y.index+y.follow[i].index;

if(v[y.follow[i].vert-1].index > -102){

list.push_back(v[y.follow[i].vert-1]);

}

list.pop_front();

}

void def(){//фунция к приведению значений по умолчанию

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

v[i].index = 10001;

v[i].visited = false;

}

void task1(){ // Решение задачи e-olymp.com №976: Флойд - существование

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

way(v[i]);

for(int j = 0; j < v.size()-1; j++){

if(!v[j].visited){

cout << 0 << " ";

}else if(v[j].index < -50){

cout << 2 << " ";

}else{

cout << 1 << " ";

}

if(!v[v.size()-1].visited){

cout << 0 ;

}else if(v[v.size()-1].index < -50){

cout << 2 ;

}else{

cout << 1 ;

}

def();

cout << endl;

}

void task2(){ // Решение задачи e-olymp.com №974: Флойд-1

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

way(v[i]);

for(int j = 0; j < v.size()-1; j++){

if(!v[j].visited){

cout << 0 << " ";

}else{

cout << v[j].index << " ";

}

if(!v[v.size()-1].visited){

cout << 0 ;

}else{

cout << v[v.size()-1].index;

}

def();

cout << endl;

}

};

int main() {

ios::sync_with_stdio(false);

int n;

cin >> n;

graph dog(n);

dog.get();

dog.task1();// Решаем задачу №976: Флойд - существование

dog.task2();// Решаем задачу №974: Флойд-1

return 0;

}

link

Related Images:

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

13/05/2015 by Осецимський Анатолій Вадимович

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

Условие задачи на e-olimp.
Cсылка на пройденный тесты.

Раз нам надо найти кратчайший путь путь, то будем использовать BFS- поиск в ширину. Мы будем постепенно просматривать вершины, внося в «план» те вершины с которыми они связанны и которые еще не внесены в «план». Для удобства я использовал вектора. В начале создаем вектор векторов, как бы это тавтологически не звучало, для этого я использовал вектор ответа, как объект, который добавлялся в вектор «graf», выступающий в роли графа, причем мы добавляем сразу к вершинам ([latex] graf[x].push_back(y);[/latex]) то есть [latex] x[/latex] — ая вершина получает связь с вершиной [latex] y[/latex], и наоборот, поскольку граф неориентированный. После чего, проверяем связанна ли начальная вершина хоть с кем — нибудь, если да, что работаем [latex] while [/latex] — ом, пока не наткнемся на начальную вершину, или все вершины в «плане» не будут пройдены. Если мы дошли до конечной вершины, то функция [latex] bfs[/latex] вернет [latex] 1[/latex], что запустит тело [latex] if [/latex]- а и мы начнем восстанавливать путь. Для этого мы заводили дополнительный вектор [latex] family[/latex], в который по мере добавления в «план», также добавлялись и вершины «отцы»(откуда пришла [latex] i [/latex] -ая вершина). Восстановленный путь записываем в вектор [latex] ans[/latex]. После чего [latex] while[/latex] прекращает свою работу и мы переходим к выводу результата. Если вектор ответа пуст, то выводим [latex]-1[/latex], иначе выводим количество вершин, участвующих в построении пути и сам путь.

link.

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

int n,m,a,b,count = 0;
vector<vector<int> > graf; vector<int> ver; vector<int> family; bool ok = false; vector<int> ans; vector<bool> popa;

int bfs(int beg, int end){ // функция которая добавляет вершины в вектор вершин,которые мы просмотрим,и помечает их как уже проверенные
    count++;
    if(beg == end){
        ok = true;
        return 1;
    }else{
        for(int i = graf[beg].size() - 1;i >= 0;i--){
            if(!popa[graf[beg][i]]){
                ver.push_back(graf[beg][i]);
                family.push_back(beg);
                popa[graf[beg][i]] = true;
            }
        }
    }
    return 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    cin >> a >> b;
    for(int i = 0 ; i <= n; i++){ // создаем векто ввекторов
            graf.push_back(ans);
            popa.push_back(false);
    }
    ver.push_back(a);family.push_back(a);
    for(int i = 0; i < m; i++){ //в вектор вершины добавляем те вершины,с которым она связанна 
        int x,y;
        cin >> x >> y;
        if(x != y){ // проверка на петлю
            graf[x].push_back(y);
            graf[y].push_back(x);
        }
    }
    if(!graf[a].empty()){ //если вершины начала не изолированна 
        while(!ok && count < ver.size() ){ //цикл,пока мы не найдем конечную вершину,или если мы не прошли все вершины в векторе "плана"
            if(bfs(ver[count],b)){ //если мы нашли выход,то начать восстанавливать пути
                count--;// Нам надо начать с последней вершины,а это count - 1 вершина
                int p = 1; //Новая переменная,которая нужна,для нахождения первого вхождения "отца" данной вершины
                ans.push_back(b);//вектор ответа
                while(ver[count] != a){ // пока не дошли до начальной вершины
                    while(ver[p] != family[count]){//двигаемся слева пройденных по вектору вершин плана,и ищем первое вхождение вершины ОТЦА
                        p++;
                    }
                    ans.push_back(ver[p]);//добавляем в ответ вершину,из которой мы попали в предыдущую (отца)
                    count = p;// теперь ищем отца отца и так далее,пока не дойдем до начальной вершины 
                    p = 1;
                }
            }
        }
        if(ans.size() > 0){ // если вектор ответа не пуст(имеет хотябы одну вершины из пути)
            cout << ans.size()-1 << endl;
            for(int i = ans.size()-1; i >= 0; i--){
                cout << ans[i] << " "; // выводим ответ справа на лево,так сказано в условии
            }
        }else{ // иначе -1
            cout << "-1\n";
        }
    }else{//если начальная вершина изолирована,то сразу выводим -1
        cout << "-1\n";
    }
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int n,m,a,b,count = 0;

vector<vector<int> > graf; vector<int> ver; vector<int> family; bool ok = false; vector<int> ans; vector<bool> popa;

int bfs(int beg, int end){ // функция которая добавляет вершины в вектор вершин,которые мы просмотрим,и помечает их как уже проверенные

count++;

if(beg == end){

ok = true;

return 1;

}else{

for(int i = graf[beg].size() - 1;i >= 0;i--){

if(!popa[graf[beg][i]]){

ver.push_back(graf[beg][i]);

family.push_back(beg);

popa[graf[beg][i]] = true;

}

return 0;

}

int main() {

ios::sync_with_stdio(false);

cin >> n >> m;

cin >> a >> b;

for(int i = 0 ; i <= n; i++){ // создаем векто ввекторов

graf.push_back(ans);

popa.push_back(false);

}

ver.push_back(a);family.push_back(a);

for(int i = 0; i < m; i++){ //в вектор вершины добавляем те вершины,с которым она связанна

int x,y;

cin >> x >> y;

if(x != y){ // проверка на петлю

graf[x].push_back(y);

graf[y].push_back(x);

}

if(!graf[a].empty()){ //если вершины начала не изолированна

while(!ok && count < ver.size() ){ //цикл,пока мы не найдем конечную вершину,или если мы не прошли все вершины в векторе "плана"

if(bfs(ver[count],b)){ //если мы нашли выход,то начать восстанавливать пути

count--;// Нам надо начать с последней вершины,а это count - 1 вершина

int p = 1; //Новая переменная,которая нужна,для нахождения первого вхождения "отца" данной вершины

ans.push_back(b);//вектор ответа

while(ver[count] != a){ // пока не дошли до начальной вершины

while(ver[p] != family[count]){//двигаемся слева пройденных по вектору вершин плана,и ищем первое вхождение вершины ОТЦА

p++;

}

ans.push_back(ver[p]);//добавляем в ответ вершину,из которой мы попали в предыдущую (отца)

count = p;// теперь ищем отца отца и так далее,пока не дойдем до начальной вершины

p = 1;

}

if(ans.size() > 0){ // если вектор ответа не пуст(имеет хотябы одну вершины из пути)

cout << ans.size()-1 << endl;

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

cout << ans[i] << " "; // выводим ответ справа на лево,так сказано в условии

}

}else{ // иначе -1

cout << "-1\n";

}

}else{//если начальная вершина изолирована,то сразу выводим -1

cout << "-1\n";

}

return 0;

}

Related Images:

e-olymp 5076. Регулярный граф

12/05/2015 by Калачьов Андрій Сергійович

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

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

Входной файл содержит числа [latex]n(1 \leq n \leq 100) [/latex] — число вершин в графе и [latex]m(1 \leq m \leq n(n — 1)/2) [/latex] — число ребер. Затем следует [latex]m [/latex] пар чисел — ребра графа.

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

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

Тесты

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

Решение:

Ссылка на ideone C++: http://ideone.com/cCHxvo

#include <iostream>
#include <vector>
using namespace std;
 
int main() {
    int m,n,f,l; bool p=true;
    cin>>n>>m;
    vector <int> a(n);
    for (int i=0; i<m; i++){
        cin>>f>>l;
        a[f-1]++; a[l-1]++;
    }
    for (int i=0; i<n; i++){if (a[i]!=a[0]){p=false; break;}}
    if (p) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
}

#include <iostream>

#include <vector>

using namespace std;

int main() {

int m,n,f,l; bool p=true;

cin>>n>>m;

vector <int> a(n);

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

cin>>f>>l;

a[f-1]++; a[l-1]++;

}

for (int i=0; i<n; i++){if (a[i]!=a[0]){p=false; break;}}

if (p) cout<<"YES"<<endl;

else cout<<"NO"<<endl;

}

Ссылка на ideone Java: http://ideone.com/2ih3iK

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner in = new Scanner(System.in);
        int m,n,f,l; 
        boolean p=true;
        n=in.nextInt();
        m=in.nextInt();
        int[] a = new int[n];
        for (int i=0; i<m; i++){
            f=in.nextInt();
            l=in.nextInt();
            a[f-1]++; a[l-1]++;
        }
        for (int i=0; i<n; i++){if (a[i]!=a[0]){p=false; break;}}
        if (p) System.out.println("YES");
        else System.out.println("NO");
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

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

{

Scanner in = new Scanner(System.in);

int m,n,f,l;

boolean p=true;

n=in.nextInt();

m=in.nextInt();

int[] a = new int[n];

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

f=in.nextInt();

l=in.nextInt();

a[f-1]++; a[l-1]++;

}

for (int i=0; i<n; i++){if (a[i]!=a[0]){p=false; break;}}

if (p) System.out.println("YES");

else System.out.println("NO");

}

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

Related Images:

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

08/05/2015 by Іванов Вячеслав Володимирович

Граф-турнир.

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

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

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

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

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

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

Реализация

ideone: http://ideone.com/XwY7fX
Засчитанное решение: http://codeforces.ru/contest/323/submission/10850799
Для решения задачи достаточно хранить граф в форме матрицы смежности.

#include <cstdio>
unsigned G[1000][1000];
int main()
{
    unsigned n; scanf("%u", &n);
    if(n == 4){
        puts("-1");
    }
    else{
	    for(size_t i = 0; i < n; i++){
	        G[i][(i+1)%n] = 1;
	    }
	    for(size_t i = 0; i < n; i++){
	        for(size_t j = 0; j < n; j++){
	            if(G[i][j] + G[j][i] == 0 && i != j){
	                if(i % 2 == j % 2)
	                    G[i][j] = 1;
	                else
	                    G[j][i] = 1;
	            }
	        }
	    }
	    for(size_t i = 0; i < n; i++){
	        for(size_t j = 0; j < n-1; j++){
	            printf("%u ", G[i][j]);
	        }
	        printf("%u\n", G[i][n-1]);
	    }
    }
    return 0;
}

#include <cstdio>

unsigned G[1000][1000];

int main()

{

unsigned n; scanf("%u", &n);

if(n == 4){

puts("-1");

}

else{

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

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

}

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

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

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

if(i % 2 == j % 2)

G[i][j] = 1;

else

G[j][i] = 1;

}

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

for(size_t j = 0; j < n-1; j++){

printf("%u ", G[i][j]);

}

printf("%u\n", G[i][n-1]);

}

return 0;

}

ideone: http://ideone.com/eBcMcY

import java.util.*;
import java.io.*;
import java.math.*;
 
class Solver {	
    public static void main(String args[]) throws IOException{
    	new Solver().run();
	}

	StreamTokenizer in;
	PrintWriter out;

	int nextInt() throws IOException{
		in.nextToken();
		return (int)in.nval;
	}
	void run() throws IOException{
		in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		out = new PrintWriter(new OutputStreamWriter(System.out));
		solve();
		out.flush();
	}
	void solve() throws IOException{
		int n = nextInt();
    	int[][] G = new int[n][n];
    	if(n == 4)
    		out.println("-1");
    	else{
    		for(int i = 0; i < n; i++)
    			G[i][(i+1)%n] = 1;
    		for(int y = 0; y < n; y++){
    			for(int x = 0; x < n; x++){
    				if(G[y][x] + G[x][y] == 0 && x != y){
    					if(y % 2 == x % 2) G[y][x] = 1;
    					else G[x][y] = 1;
    				}
    			}
    		}
    		for(int y = 0; y < n; y++){
    			for(int x = 0; x < n-1; x++){
    				out.print(G[y][x]);
    				out.print(" ");
    			}
    			out.println(G[y][n-1]);
    		}
    	}
	}
}

import java.util.*;

import java.io.*;

import java.math.*;

class Solver {

public static void main(String args[]) throws IOException{

new Solver().run();

}

StreamTokenizer in;

PrintWriter out;

int nextInt() throws IOException{

in.nextToken();

return (int)in.nval;

}

void run() throws IOException{

in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

out = new PrintWriter(new OutputStreamWriter(System.out));

solve();

out.flush();

}

void solve() throws IOException{

int n = nextInt();

int[][] G = new int[n][n];

if(n == 4)

out.println("-1");

else{

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

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

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

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

if(G[y][x] + G[x][y] == 0 && x != y){

if(y % 2 == x % 2) G[y][x] = 1;

else G[x][y] = 1;

}

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

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

out.print(G[y][x]);

out.print(" ");

}

out.println(G[y][n-1]);

}

Related Images:

e-olimp 5074. Степени вершин по спискам ребер

02/05/2015 by Карташов Денис Геннадійович

Задача:

Неориентированный граф задан списком ребер.

Найдите степени всех вершин графа.

Технические условия:

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

Входной файл содержит числа [latex]n[/latex] [latex] (1 \leq n \leq 100) [/latex] — число вершин в графе и

[latex]m[/latex] [latex](1 \leq m \leq \frac{n(n-1)}{2})[/latex] — число ребер. Затем следует [latex]m[/latex] пар чисел — ребра графа.

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

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

Результат на C++

Результат на Java

Код на C++:

#include <iostream>
using namespace std;

int main() {
   int n = 0 , m = 0, i, buf;
   cin >> n >> m;
   int *a = new int [n];
   for(i = 0; i < n; a[i] = 0, ++i);
   for(i = 0 , buf; i < 2*m ; cin >> buf, ++a[buf - 1], ++i);
   for(i = 0; i < n; ++i){
   		 cout << a[i] << endl;
   }
   return 0;
}

#include <iostream>

using namespace std;

int main() {

int n = 0 , m = 0, i, buf;

cin >> n >> m;

int *a = new int [n];

for(i = 0; i < n; a[i] = 0, ++i);

for(i = 0 , buf; i < 2*m ; cin >> buf, ++a[buf - 1], ++i);

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

cout << a[i] << endl;

}

return 0;

}

Код на Java:

import java.io.*;
import java.util.*;

public class Main
{
	public static void main (String[] args)
	{
		Scanner in = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		int n, m, i, buf;
		n = in.nextInt();
		m = in.nextInt();
		int[] a = new int [n];
		for(i = 0; i < n; a[i] = 0, ++i);
		for(i = 0; i < 2*m ;buf = in.nextInt(), ++a[buf - 1], ++i);
		for(i = 0; i < n; ++i){
			out.println(a[i]);
		}
		out.flush();
	}
}

import java.io.*;

import java.util.*;

public class Main

{

public static void main (String[] args)

{

Scanner in = new Scanner(System.in);

PrintWriter out = new PrintWriter(System.out);

int n, m, i, buf;

n = in.nextInt();

m = in.nextInt();

int[] a = new int [n];

for(i = 0; i < n; a[i] = 0, ++i);

for(i = 0; i < 2*m ;buf = in.nextInt(), ++a[buf - 1], ++i);

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

out.println(a[i]);

}

out.flush();

}

Описание:

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

Related Images:

e-olimp 5075

30/04/2015 by Денисова Ольга

Задача Ориентированный граф задан списком ребер. Найдите степени всех вершин графа.
Входные данные. Входной файл содержит числа [latex]n[/latex] [latex]\left(1\leq n\leq 100\right)[/latex] — число вершин в графе и [latex]m[/latex] [latex]\left(1\leq m\leq n*\left(n-1\right)\right)[/latex] — число ребер. Затем следует [latex]m[/latex] пар чисел — ребра графа.

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

Тесты

Результат

Комментарии

4 41 21 3

2 3

3 4

0 21 12 1

1 0

пройден

4 1
3 2

0 01 00 1

0 0

пройден

Решение

#include <iostream>
using namespace std;

int main() {
	int n, m, a, b;
	cin >> n >> m;
	int res[n][2];
	for(int i = 0 ; i < n; i++) {
			res[i][1] = 0;
			res[i][0] = 0;
	}
	for(int i = 0; i < m; i++) {
		cin >> a >> b;
		res[b - 1][0]++;
		res[a - 1][1]++;
	}
	for(int i = 0; i < n; i++) {
		cout << res[i][0] << " " << res[i][1] << endl;
	}
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, m, a, b;

cin >> n >> m;

int res[n][2];

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

res[i][1] = 0;

res[i][0] = 0;

}

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

cin >> a >> b;

res[b - 1][0]++;

res[a - 1][1]++;

}

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

cout << res[i][0] << " " << res[i][1] << endl;

}

return 0;

}

Решение на Java:

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int a, b;
		//число вершин графа
		int n = in.nextInt();
		//Число ребер
		int m = in.nextInt();
		int res[][];
		
		//Иницилизация и обнуление двумерного массива 
		// res[номер вершины][0-количество заходов 1-количество исходов] 
		res = new int [n][];
		for(int i = 0 ; i < n; i++) {
			res[i] = new int [2];
			res[i][1] = 0;
			res[i][0] = 0;
		}
		
		// в каждом элементе цикла вводим ребро и для соответствующих вершин увеличиваем счетчик
		for(int i = 0; i < m; i++) {
			// ввод ребра графа a-номер вершины исхода b-номер вершины захода
			a = in.nextInt();
			b = in.nextInt();
			res[b - 1][0]++;
			res[a - 1][1]++;
		}
		// Вывод в выходной файл n пар чисел - для каждой вершины сначала полустепень захода и затем полустепень исхода. 
		for(int i = 0; i < n; i++) {
			System.out.printf(Locale.US,"%d %d\n",res[i][0],res[i][1]); 
		}
	}
}

import java.util.*;

import java.io.*;

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

int a, b;

//число вершин графа

int n = in.nextInt();

//Число ребер

int m = in.nextInt();

int res[][];

//Иницилизация и обнуление двумерного массива

// res[номер вершины][0-количество заходов 1-количество исходов]

res = new int [n][];

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

res[i] = new int [2];

res[i][1] = 0;

res[i][0] = 0;

}

// в каждом элементе цикла вводим ребро и для соответствующих вершин увеличиваем счетчик

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

// ввод ребра графа a-номер вершины исхода b-номер вершины захода

a = in.nextInt();

b = in.nextInt();

res[b - 1][0]++;

res[a - 1][1]++;

}

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

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

System.out.printf(Locale.US,"%d %d\n",res[i][0],res[i][1]);

}

Related Images:

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

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

Задача e-olimp 4000

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

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

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

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

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

Пример:

Входные данные	Выходные данные
5 1	3
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

Решение

#include <iostream>
#include <stack>
using namespace std;

int main()
	{
		int n;
		int s;
		cin>>n>>s;
		s--;
		int matrix[n][n];
		stack<int> st;
		int counter=1;
		for(int i=0;i<n;i++)
			{
				for(int j=0;j<n;j++)
					{
						cin>>matrix[i][j];
					}
			}
		for(int j=0;j<n;j++)
			{
				if(matrix[s][j] == 1) st.push(j);
			}
		matrix[s][s]=1;
		while(!st.empty())
			{
				int a=st.top();
				st.pop();
				if(matrix[a][a]!=1)
					{
						for(int j=0;j<n;j++)
							{
								if(matrix[a][j] == 1) st.push(j);
							}
						counter++;
						matrix[a][a]=1;
					}
				
			}
		cout<<counter<<endl;
	}

#include <iostream>

#include <stack>

using namespace std;

int main()

{

int n;

int s;

cin>>n>>s;

s--;

int matrix[n][n];

stack<int> st;

int counter=1;

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

{

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

{

cin>>matrix[i][j];

}

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

{

if(matrix[s][j] == 1) st.push(j);

}

matrix[s][s]=1;

while(!st.empty())

{

int a=st.top();

st.pop();

if(matrix[a][a]!=1)

{

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

{

if(matrix[a][j] == 1) st.push(j);

}

counter++;

matrix[a][a]=1;

}

cout<<counter<<endl;

}

import java.util.*;
import java.lang.*;
import java.io.*;

class Ideone
{
	public static void main (String[] args)
	{
		Scanner in = new Scanner(System.in);
        int n = in.nextInt(), s = in.nextInt()-1, counter = 1;
		int[][] matrix = new int[n][n];
		Stack st = new Stack();
		for(int i = 0;i < n; i++)
			{
				for(int j = 0;j < n; j++)
					{
						matrix[i][j] = in.nextInt();
					}
			}
		for(int j = 0; j < n; j++)
			{
				if(matrix[s][j] == 1) st.push(j);
			}
		matrix[s][s] = 1;
		while(!st.empty())
			{
				int a = (int) st.peek();
				st.pop();
				if(matrix[a][a] != 1)
					{
						for(int j = 0; j < n; j++)
							{
								if(matrix[a][j] == 1) st.push(j);
							}
						counter++;
						matrix[a][a] = 1;
					}
				
			}
		System.out.println(counter);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

public static void main (String[] args)

{

Scanner in = new Scanner(System.in);

int n = in.nextInt(), s = in.nextInt()-1, counter = 1;

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

Stack st = new Stack();

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

{

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

{

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

}

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

{

if(matrix[s][j] == 1) st.push(j);

}

matrix[s][s] = 1;

while(!st.empty())

{

int a = (int) st.peek();

st.pop();

if(matrix[a][a] != 1)

{

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

{

if(matrix[a][j] == 1) st.push(j);

}

counter++;

matrix[a][a] = 1;

}

System.out.println(counter);

}

Вводим данные, затем в первом цикле проверяем строку [latex]s[/latex], и записываем в стек все вершины инцидентные данной. Так как в условии гарантируется наличие на главной диагонали нулей, то будем помечать проверенные вершины с помощью элемента расположенного на главной диагонали (то есть будем присваивать ему значение отличное от 0, к примеру 1). После будем проверять все строки в стеке до его опустошения, и увеличивать счётчик на единицу после удаления из стека не помеченной вершины.

Код на ideone.

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

Related Images:

e-olimp 5080. Количество висячих вершин 1

29/04/2015 by Марченко Філіп Олександрович

Код:

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

int gr[1001][1001]; // матрица смежности
int n; //кол-во вершин
	
//Просматривая матрицу смежности, подсчитываем кол-во единиц, т.е кол-во
//инцидентных вершин данной вершине. Инцидентные вершины - вершины, которые соединены ребром. Степенью вершины называется кол-во рёбер, инцидентных этой вершине.
//Висячей вершиной называют вершину, степень которой равна 1. Соответственно, если в каком-либо ряду в матрице 
//только одна единица, то вершина имеет степень 1 и является висячей.

int main() {
	ios::sync_with_stdio(false);
	cin >> n;
	int ans = 0; //предположим, что граф не имеет висячих вершин 
	for (int i=0; i<n; i++)
		for (int j=0; j<n; j++)
			cin >> gr[i][j];	//ввод матрицы смежности
	for (int i=0; i<n; i++){
		int cnt = 0; //счётчик
		for (int j=0; j<n; j++){
			if (gr[i][j] == 1) cnt++;  //подсчёт степени
		}
		if (cnt==1) ans++;  //проверка на висячую вершину
	}
	cout << ans << endl;	//вывод ответа
	return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int gr[1001][1001]; // матрица смежности

int n; //кол-во вершин

//Просматривая матрицу смежности, подсчитываем кол-во единиц, т.е кол-во

//инцидентных вершин данной вершине. Инцидентные вершины - вершины, которые соединены ребром. Степенью вершины называется кол-во рёбер, инцидентных этой вершине.

//Висячей вершиной называют вершину, степень которой равна 1. Соответственно, если в каком-либо ряду в матрице

//только одна единица, то вершина имеет степень 1 и является висячей.

int main() {

ios::sync_with_stdio(false);

cin >> n;

int ans = 0; //предположим, что граф не имеет висячих вершин

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

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

cin >> gr[i][j]; //ввод матрицы смежности

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

int cnt = 0; //счётчик

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

if (gr[i][j] == 1) cnt++; //подсчёт степени

}

if (cnt==1) ans++; //проверка на висячую вершину

}

cout << ans << endl; //вывод ответа

return 0;

}

Related Images:

e-olimp 5077. Полуполный граф

27/04/2015 by Бронфен-Бова Роман

Задача: Полуполный граф

Решение

ссылка на ideone, засчитанное решение на e-olymp

#include<iostream>
using namespace std;

bool used[101][101];

int main(){
  int n, m; cin >> n >> m;
  for(int i = 0; i < m; i++){
     int a,b; cin >> a >> b;
     used[a][b] = used[b][a] = 1;
  }
  for(int i = 1; i <= n; i++){
     for(int j = i+1; j <= n; j++){
        if(used[i][j] == false){
           cout << "NO\n";
           return 0;
        }
     }
  }
  cout << "YES\n";
  return 0;
}

#include<iostream>

using namespace std;

bool used[101][101];

int main(){

int n, m; cin >> n >> m;

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

int a,b; cin >> a >> b;

used[a][b] = used[b][a] = 1;

}

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

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

if(used[i][j] == false){

cout << "NO\n";

return 0;

}

cout << "YES\n";

return 0;

}

Решение на Java

ссылка на ideone, засчитанное решение на e-olymp

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Main
{
	static boolean[][] used = new boolean[101][101];
	static Scanner sc = new Scanner(System.in);
 
	public static void main (String[] args) throws java.lang.Exception
	{
		int n, m;
		n = sc.nextInt();
		m = sc.nextInt();
		for(int i = 0; i < m; i++){
	     	int a, b;
	     	a = sc.nextInt();
	     	b = sc.nextInt();
	    	used[a][b] = used[b][a] = true;
	  	}
		for(int i = 1; i <= n; i++){
	    	for(int j = i+1; j <= n; j++){
	    		if(used[i][j] == false){
	    			System.out.println("NO");
	           		return;
	        	}
	    	}
	  	}
	  	System.out.println("YES");
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

static boolean[][] used = new boolean[101][101];

static Scanner sc = new Scanner(System.in);

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

{

int n, m;

n = sc.nextInt();

m = sc.nextInt();

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

int a, b;

a = sc.nextInt();

b = sc.nextInt();

used[a][b] = used[b][a] = true;

}

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

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

if(used[i][j] == false){

System.out.println("NO");

return;

}

System.out.println("YES");

}

Идея решения

Считаем что граф неорентированный и проверяем, не полный ли наш граф. Если полный — выводим «YES», иначе «NO».

Related Images:

e-olimp 4856. Кратчайший путь

24/04/2015 by Ілларіонова Марія Валеріївна

Задача e-olimp.com №4856. Ссылка на засчитанное решение.

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

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

Первая строка содержит натуральные числа [latex]n[/latex] и [latex]m[/latex] [latex]\left(n\leq 2000, m\leq 50000 \right)[/latex] — количество вершин и рёбер графа. Вторая строка содержит натуральные числа [latex]s[/latex] и [latex]f[/latex] [latex]\left(1\leq s, f\leq n, s\neq f \right)[/latex] — номера вершин, длину пути между которыми требуется найти. Следующие [latex]m[/latex] строк содержат по три числа [latex]b_{i}[/latex], [latex]e_{i}[/latex] и [latex]w_{i}[/latex]- номера концов [latex]i[/latex]-ого ребра и его вес соответственно [latex]\left(1 \leq b_{i}, e_{i}\leq n, 0\leq w_{i}\leq 100000\right)[/latex].

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

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

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

#include <iostream> 
#include <vector>
#include <set>
#include <utility>
using namespace std;
#define INF 1000000000000
#define MAX 100000

vector <pair <int, long long> > G[MAX];
vector <int> path;
vector <int> ans;
set <pair <long long, int> > q;
long long length[MAX];
int parent[MAX];

int main() {
    ios::sync_with_stdio(false);
    int n, m, a, b;
    cin >> n >> m >> a >> b;
    a--, b--; // начнём отсчёт с 0, для удобства
    for (int i=0; i<m; i++) {
        int from, to, len;
        cin >> from >> to >> len;
        from--, to--;
        G[to].push_back(make_pair(from, len));
        G[from].push_back(make_pair (to, len));
    }
    for (int i=0; i<n; i++) length[i]=INF;
    length[a]=0;
    q.insert (make_pair (length[a], a));
    while (!q.empty()) { // будем выполнять, пока наша очередь не пуста
        int v = q.begin()->second;
        q.erase (q.begin());
        for (int i=0; i<G[v].size(); i++) {
            int to=G[v][i].first, len=G[v][i].second;
            if (length[v]+len<length[to]) { // изначально она бесконечно большая, поэтому сразу меньше, а если будет оказываться больше, то просто не будем менять
                   q.erase (make_pair (length[to], to)); // мы убираем нашу бесконечность или больший путь вместе со следующей вершиной, а вместо них
                   length[to]=length[v]+len; // ставим новую длину
                   parent[to]=v; // и записываем предка
                   q.insert (make_pair (length[to], to));
            }
        }
    }
    if (length[b]==INF) { // если последняя вершина оказалась бесконечностью, значит, мы её не достигли
        cout << "-1"; 
        return 0;
    } 
    cout << length[b] << endl;
    int c=b;
    while (c!=a) {
        ans.push_back(c+1); // так как начинали с 1, то увеличиваем
        c=parent[c];
    }
    ans.push_back(a+1);
    cout << ans[ans.size()-1];
    for(int it = ans.size()-2; it >=0; it--) cout << " " << ans[it];
    cout << endl;
    return 0;   
}

#include <iostream>

#include <vector>

#include <set>

#include <utility>

using namespace std;

#define INF 1000000000000

#define MAX 100000

vector <pair <int, long long> > G[MAX];

vector <int> path;

vector <int> ans;

set <pair <long long, int> > q;

long long length[MAX];

int parent[MAX];

int main() {

ios::sync_with_stdio(false);

int n, m, a, b;

cin >> n >> m >> a >> b;

a--, b--; // начнём отсчёт с 0, для удобства

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

int from, to, len;

cin >> from >> to >> len;

from--, to--;

G[to].push_back(make_pair(from, len));

G[from].push_back(make_pair (to, len));

}

for (int i=0; i<n; i++) length[i]=INF;

length[a]=0;

q.insert (make_pair (length[a], a));

while (!q.empty()) { // будем выполнять, пока наша очередь не пуста

int v = q.begin()->second;

q.erase (q.begin());

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

int to=G[v][i].first, len=G[v][i].second;

if (length[v]+len<length[to]) { // изначально она бесконечно большая, поэтому сразу меньше, а если будет оказываться больше, то просто не будем менять

q.erase (make_pair (length[to], to)); // мы убираем нашу бесконечность или больший путь вместе со следующей вершиной, а вместо них

length[to]=length[v]+len; // ставим новую длину

parent[to]=v; // и записываем предка

q.insert (make_pair (length[to], to));

}

if (length[b]==INF) { // если последняя вершина оказалась бесконечностью, значит, мы её не достигли

cout << "-1";

return 0;

}

cout << length[b] << endl;

int c=b;

while (c!=a) {

ans.push_back(c+1); // так как начинали с 1, то увеличиваем

c=parent[c];

}

ans.push_back(a+1);

cout << ans[ans.size()-1];

for(int it = ans.size()-2; it >=0; it--) cout << " " << ans[it];

cout << endl;

return 0;

}

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

Related Images:

e-olimp 5078. Турнир

22/04/2015 by Ілларіонова Марія Валеріївна

Задача e-olimp.com №5078.

Ссылка на засчитанное решение (C++).

Ссылка на засчитанное решение (Java).

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

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

Входной файл содержит числа [latex]n \left(1\leq n\leq 100 \right)[/latex] — число вершин в графе и [latex]m \left(1\leq m\leq n\left(n-1 \right) \right)[/latex] — число ребер. Затем следует [latex]m[/latex] пар чисел — ребра графа.

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

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

Код программы (С++):

#include <iostream>
using namespace std;

int A[110][110];

int main() {
	ios::sync_with_stdio(false);
	int n, m, a, b;
	cin >> n >> m;
	for (int i=0; i<m; i++) {
		cin >> a >> b;
		a--;
		b--;
		A[a][b]=1;
	}
	for (int i=0; i<n; i++) {
		for (int j=i+1; j<n; j++) {
			if (A[i][j]==1) {
				if (A[j][i]==1) {
					cout << "NO\n";
					return 0;
				}
			}
			else {
				if (A[j][i]==0) {
					cout << "NO\n";
					return 0;
				}
			}
		}
	}
	cout << "YES\n";
	return 0;
}

#include <iostream>

using namespace std;

int A[110][110];

int main() {

ios::sync_with_stdio(false);

int n, m, a, b;

cin >> n >> m;

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

cin >> a >> b;

a--;

b--;

A[a][b]=1;

}

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

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

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

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

cout << "NO\n";

return 0;

}

else {

if (A[j][i]==0) {

cout << "NO\n";

return 0;

}

cout << "YES\n";

return 0;

}

Java:

import java.util.*;
import java.lang.*;
import java.io.*;

class Ideone {
	public static void main (String[] args) {
		Scanner in = new Scanner (System.in);
		int n, m, a, b;
		n = in.nextInt();
		m = in.nextInt();
		boolean [][] A = new boolean[n][n];
		for (int i=0; i<m; i++) {
			a = in.nextInt();
			b = in.nextInt();
			a--;
			b--;
			A[a][b]=true;
		}
		boolean f = false;
		for (int i=0; i<n; i++) {
			for (int j=i+1; j<n; j++) {
				if (A[i][j] && A[j][i]) {
					System.out.println("NO");
					f = true;
					break;
				}
				else if (!A[i][j] && !A[j][i]) {
					System.out.println("NO");
					f = true;
					break;
				}
			}
		}
		if (!f) System.out.println("YES");
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone {

public static void main (String[] args) {

Scanner in = new Scanner (System.in);

int n, m, a, b;

n = in.nextInt();

m = in.nextInt();

boolean [][] A = new boolean[n][n];

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

a = in.nextInt();

b = in.nextInt();

a--;

b--;

A[a][b]=true;

}

boolean f = false;

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

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

if (A[i][j] && A[j][i]) {

System.out.println("NO");

f = true;

break;

}

else if (!A[i][j] && !A[j][i]) {

System.out.println("NO");

f = true;

break;

}

if (!f) System.out.println("YES");

}

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

Далее программа пробегает цикл по матрице смежности выше главной диагонали (так как на самой диагонали могут быть лишь петли, а в условии оговорено, что вершины должны быть различны). Если в таблице встречается 1, то мы должны проверить, если ли ребро, обратное данному. Если нет — продолжаем, есть — говорим, что граф не турнир и завершаем работу программы. Если же у нас не встретилось 1, то мы проверяем, есть ли обратное ребро. Если его нет, то мы говорим, что связи между этими двумя вершинами не существует, а следовательно наш граф — не турнир (завершаем программу).

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