Şəhərlər və yollar (Həll təhlili)

Tutaq ki, $g$ — qrafın qonşuluq matrisidir. Qraf istiqamətləndirilməmiş olduğundan, $i$ və $j$ təpələri arasında tərəf olduqda aşağıdakı bərabərliklər doğrudur:

Qrafdakı tərəflərin sayı qonşuluq matrisindəki vahidlərin sayının $2$-yə bölünməsinə bərabərdir.

Misal

Misalda verilmiş qraf aşağıdakı kimidir:

Planetdəki yolların sayı $3$-ə bərabərdir.

Alqoritmin realizasiyası

$n$ giriş qiymətini oxuyuruq.

scanf("%d",\&n);

Qonşuluq matrisini oxuyuruq. Ondakı ədədlərin $res$ cəmini hesablayırıq. Qraf istiqamətləndirilməmiş olduğundan, $res$ tərəflərin sayının ikiqat böyüklüyünə bərabərdir.

res = 0;
for(i = 0; i \< n; i++)
for(j = 0; j \< n; j++)
{
  scanf("%d",\&val);
  res += val;
}

Tərəflərin sayını hesablayıb çıxarırıq.

res /= 2;
printf("%d\n",res);

Java realizasiyası

import java.util.*;

public class Main
{
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    int n = con.nextInt();

    int res = 0;
    for(int i = 0; i \< n; i++)
    for(int j = 0; j \< n; j++)
      res += con.nextInt();

    res /= 2;
    System.out.println(res);
    con.close();
  }
}

Python realizasiyası — gedişat zamanı

$n$ giriş qiymətini oxuyuruq.

n = int(input())

Qonşuluq matrisindəki ədədlərin cəmini $res$ dəyişənində hesablayırıq.

res = 0

Qonşuluq matrisini sətir-sətir oxuyuruq. Hər sətir üçün ondakı ədədlərin cəmini hesablayırıq. Sonra bu cəmi $res$ qiymətinə əlavə edirik.

for _ in range(n):
  res += sum(map(int, input().split()))

Qraf istiqamətləndirilməmiş olduğundan, $res$ cəmi tərəflərin sayının ikiqat böyüklüyünə bərabərdir. $res$-i $2$-yə bölüb cavabı çıxarırıq.

res //= 2
print(res)

Python realizasiyası — qonşuluq matrisi

Giriş məlumatlarını oxuyuruq.

n = int(input()) 
g = [[int(j) for j in input().split()] for i in range(n)]

Qonşuluq matrisindəki ədədlərin $s$ cəmini hesablayırıq. Qraf istiqamətləndirilməmiş olduğundan, $s$ tərəflərin sayının ikiqat böyüklüyünə bərabərdir.

s = 0
for row in g:
  s += sum(row)

Tərəflərin sayını çıxarırıq.

print(s // 2)