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

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

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

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

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

Код

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

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

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

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

C++

#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++

#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++

#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 случая:

Код

//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. Я сделал проверку на еденицу и всё прошло...

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

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

@D_in_practice 343 / 343 / 331 Регистрация: 02.10.2014 Сообщений: 666
	10.11.2014, 17:03	6
	_Ivana, +1, mr_free, если надо решить не эту задачу, то какую? возьмем три города и 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 0

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