Задача "Города и дороги"

@mr_free · Регистрация: 08.08.2012

Студворк — интернет-сервис помощи студентам

Здравствуйте!

Решаю задачу, но моё решение не проходит на 100%, а всего лишь на 50%. Помогите-подскажите, что я делаю не так.
Условие:

Code
1
Есть N городов, некоторые из которых соединены дорогами. Нужно сосчитать количество дорог.

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

В первой строке записано число N (0 ≤ N ≤ 100). В следующих N строках записано по N чисел, каждое из которых является единичкой или ноликом. Причем, если в позиции (i, j) квадратной матрицы стоит единичка, то i-ый и j-ый города соединены дорогами, а если нолик, то не соединены.

Выходные данные:
Количество дорог.
Моё решение:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
 
using namespace std;
 
int main()
{
   int n;
   cin >> n;
   int a[n][n];
   for (int i=1; i<=n; i++)
       for (int j=1; j<=n; j++)
   {
       cin >> a[i][j];
   }
   int res = 0;
   for (int i=1; i<=n; i++)
       for (int j=i+1; j<=n; j++)
   {
       res +=a[i][j];
   }
   cout << res << endl;
   return 0;
}

@_Ivana · 09.11.2014, 19:41

По-русски говоря, неориентированный граф задан матрицей смежности? Надо сложить всю матрицу и поделить на 2.

Добавлено через 4 минуты
У вас это точно компилируется? Объявление массива неконстантного размера, обращение к нему за пределами индекса... В Матлабе примерно такой код скомпилировался и наверное даже заработал бы

@ReinDeer · 09.11.2014, 20:15

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <stdio.h>
int main(){
    int n;
    scanf("%d",&n);
    int k=0;
    bool **Arr= new bool*[n];
    for (int i=0;i<n;i++)
        Arr[i] = new bool[n];
    for (int i=0;i<n;i++)
        for (int j=0;j<n;j++){
            scanf("%d",&Arr[i][j]);
            if (Arr[i][j]==1)
                k++;
        }
    printf("%d",k);
}

Так я понял задачу. Есть вопросы - отвечу.

@mr_free · 09.11.2014, 21:53 **[ТС]**

_Ivana, да это у меня компилится и я рад, а то через указатели еще не нашарился. (GCC 4.7) . Я складываю и делю, но проходит только половина тестов. Что не так?
ReinDeer, задачу Вы поняли не совсем верно. Потому как просто пройти посчитать единицы - не выход.

@ReinDeer · 09.11.2014, 21:58

Не по теме:

mr_free, действительно, глупо сделал.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <stdio.h>
int main(){
    int n;
    scanf("%d",&n);
    int k=0;
    bool **Arr= new bool*[n];
    for (int i=0;i<n;i++)
        Arr[i] = new bool[n];
    for (int i=0;i<n;i++)
        for (int j=0;j<n;j++){
            scanf("%d",&Arr[i][j]);
            if (Arr[i][j]==1){
                k++;
                Arr[j][i]=0;//обнуляем повторы.
            }
        }
    printf("%d",k);
}

Все равно не то.

@D_in_practice · 10.11.2014, 17:03

_Ivana, +1,
mr_free, если надо решить не эту задачу, то какую?
возьмем три города и 4 случая:

Code
1
2
3
4
//1-2           2-3        1-2, 2-3     1-2, 2-3, 1-3
0 1 0         0 0 1           0 1 0             0 1 1
1 0 0         0 0 0           1 0 1             1 0 1
0 0 0         1 0 0           0 1 0             1 1 0

1 и 2 случаи - 1 дорога = число единиц / 2
3 вариант - 2 дороги = число единиц / 2
4 вариант - 3 дороги = число единиц / 2

@Dani · 10.11.2014, 17:18

Дальнейшие рассуждения основываются на том, что граф задан матрицей смежности.
Если граф неориентированный, тогда такие циклы:

C++
1
2
3
for(int i = 0; i < n; ++i)
 for(int j = i; j < n; ++j)
  result += a[i][j];

Если же он ориентированный, то

C++
1
2
3
for(int i = 0; i < n; ++i)
 for(int j = 0; j < n; ++j)
   result += a[i][j];

Как я понял условие, то нигде не сказано, что граф неориентированный.

@mr_free · 23.11.2014, 22:17 **[ТС]**

D_in_practice, Dani, вы правы.
Всё было весьма тупо: просто в условие не указано, что массив может заполняться только 0 и 1. Я сделал проверку на еденицу и всё прошло...

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer 8Observer8 08.02.2026 Содержание блога Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .	SDL3 для Web (WebAssembly): Основы отладки веб-приложений на SDL3 по USB и Wi-Fi, запущенных в браузере мобильных устройств 8Observer8 07.02.2026 Содержание блога Браузер Chrome имеет средства для отладки мобильных веб-приложений по USB. В этой пошаговой инструкции ограничимся работой с консолью. Вывод в консоль - это часть процесса. . .	SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .
SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .

@_Ivana 4949 / 2289 / 287 Регистрация: 01.03.2013 Сообщений: 5,991 Записей в блоге: 32
	09.11.2014, 19:41
	По-русски говоря, неориентированный граф задан матрицей смежности? Надо сложить всю матрицу и поделить на 2. Добавлено через 4 минуты У вас это точно компилируется? Объявление массива неконстантного размера, обращение к нему за пределами индекса... В Матлабе примерно такой код скомпилировался и наверное даже заработал бы 1

@mr_free 73 / 7 / 0 Регистрация: 08.08.2012 Сообщений: 223 Записей в блоге: 1
	09.11.2014, 21:53 [ТС]
	_Ivana, да это у меня компилится и я рад, а то через указатели еще не нашарился. (GCC 4.7) . Я складываю и делю, но проходит только половина тестов. Что не так? ReinDeer, задачу Вы поняли не совсем верно. Потому как просто пройти посчитать единицы - не выход. 0

@mr_free 73 / 7 / 0 Регистрация: 08.08.2012 Сообщений: 223 Записей в блоге: 1
	23.11.2014, 22:17 [ТС]
	D_in_practice, Dani, вы правы. Всё было весьма тупо: просто в условие не указано, что массив может заполняться только 0 и 1. Я сделал проверку на еденицу и всё прошло... 0