Nəqliyyat Sistemi#9635

Nəqliyyat Sistemi (Həll təhlili)

Gəlin, qaynaq təpə $s$ və təyinat vertex $f$ -dən başlayaraq genişliyinə birinci axtarış həyata keçirək. $d i s tS$ massivində $s$ -dən olan ən qısa məsafələri və $d i s tF$ massivində $f$ -dən olan ən qısa məsafələri saxlayın.

Qeyd: $o pt D i s t an ce$ optDistance $s$ və $f$ arasında olan qısadır.

İndi, $i$ və $j$ düyünlər arasında yeni bir yol tikmə imkanını nəzərdən keçirək.

Qrafa $(i, j)$ yolunu əlavə etdikdə, yeni yollar yaradılır:

s \to i \to j \to f u z u n l u q d i s tS [i] + 1 + d i s tF [j], s \to j \to i \to f u z u n l u q d i s tS [j] + 1 + d i s tF [i]

s → i → j → f~uzunluq~distS[i] + 1 + distF[j], \\ s → j → i → f~uzunluq~distS[j] + 1 + distF[i]

Əgər bu məsafələrdən hər hansı biri $o pt D i s t an ce$ optDistance-dən kiçikdirsə, bu halda $(i, j)$ yolunun əlavə edilməsi $s$ və $f$ arasında olan ən qısa məsafənin azalmasına səbəb olacaq və buna görə də uyğundur.

İndi bütün mümkün cütləri $(i, j)$ yoxlamaq və yeni bir yolun əlavə edilməsi $s$ və $f$ arasında olan ən qısa məsafəni azaldıb-azaltmayacağını təsdiq etməliyik.

Misal

Birinci testin qrafi solda göstərilib. Tepə $1$ -dən təpə $5$ -ə olan ən qısa məsafə $4$ -dür. Hansı yeni yolu əlavə etsək də, bu məsafə azalacaq. Buna görə də tələb olunan yollar mövcud deyil.

İkinci testin qrafi sağda göstərilib. Tepə $3$ -dən tepe $5$ -ə ən qısa məsafə $2$ -dir. Mümkün yeni yollar qalın xətlərlə işarələnmişdir. Bu yollardan hansını seçməyimizdən asılı olmayaraq, $3$ və $5$ arasındakı məsafə azalmayacaqdır.

Alqoritm tətbiqi

$M A X$ sabitini müəyyənləşdirin — qrafa mümkün olan ən çox sayda vertex.

#define MAX 1001

Əlaqə matrisini $g$ və ən qısa məsafələr üçün massivləri bəyan edin.

int g[MAX][MAX], distS[MAX], distF[MAX];

bfs funksiyası vertexdən $s t a r t$ -da genişliyinə birinci axtarışı yerinə yetirir. Ən qısa məsafələrin saxlanılacağı $d i s t$ massivini qəbul edir.

void bfs(int start, int *dist)
{

Ən qısa məsafələrin massivi $d i s t$ -i başladın.

  for (int i = 0; i <= n; i++) dist[i] = -1;
  dist[start] = 0;

Bir sıra $q$ bəyan edin və başlayaq vertex $s t a r t$ -ı oraya əlavə edin.

  queue<int> q;
  q.push(start);

Növbədə vertex $v$ boş olmayana qədər çıxarın.

  while (!q.empty())
  {
    int v = q.front(); q.pop();

Bütün vertexlər $t o$ -u $v$ -yə bitişik olaraq keçirin. Əgər $t o$ vertexi hələ ziyarət edilməyibsə, ən qısa məsafəni $d i s t [t o]$ dist[to] hesablayın və onu növbəyə əlavə edin.

    for (int to = 1; to <= n; to++)
      if (g[v][to] && dist[to] == -1)
      {
        q.push(to);
        dist[to] = dist[v] + 1;
      }
  }
}

C++

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyun.

scanf("%d %d %d %d", &n, &m, &s, &f);
memset(g, 0, sizeof(g));

Yönsüz qrafı oxuyun.

for (i = 0; i < m; i++)
{
  scanf("%d %d", &a, &b);
  g[a][b] = g[b][a] = 1;
}

Tepələrdən $s$ və $f$ -dən genişliyinə birinci axtarışı həyata keçirin. Ən qısa məsafələr $d i s tS$ və $d i s tF$ massivlərinə saxlanılır.

bfs(s, distS);
bfs(f, distF);

Qeyd edək ki, $o pt D i s t an ce$ optDistance orijinal qrafda $s$ və $f$ arasındakı ən qısa məsafədir.

optDistance = distS[f];

Bütün vertex cütlərini $i$ və $j$ boyunca keçirin və aralarında yeni bir yol tikmə imkanını nəzərdən keçirin. $r es$ dəyişəni bu cür uyğun yolların sayını izləyir.

res = 0;
for (i = 1; i <= n; i++)
for (j = i + 1; j <= n; j++)

Əgər $i$ və $j$ vertexlər arasında heç bir yol yoxdursa, $s \to i \to j \to f$ s → i → j → f və $s \to j \to i \to f$ s → j → i → f ən qısa yolların uzunluğunu hesablayın. Əgər bu məsafələrin hər ikisi $o pt D i s t an ce$ optDistance-dən az deyilsə, onda bu cür yol tikilməlidir.

  if (g[i][j] == 0)
  {
     if ((distS[i] + distF[j] + 1 >= optDistance) &&
         (distS[j] + distF[i] + 1 >= optDistance))
       res++;
  }

Cavabı çap edin.

printf("%d\n", res);

Java tətbiqi

import java.util.*;

public class Main
{
  static int g[][], distS[], distF[];
  static int n, m, s, f;
  
  static void bfs(int start, int dist[])
  {
    Arrays.fill(dist,-1);
    dist[start] = 0;

    Queue<Integer> q = new LinkedList<Integer>();
    q.add(start);

    while(!q.isEmpty())
    {
      int v = q.poll();
      for (int to = 1; to <= n; to++)
        if (g[v][to] == 1 && dist[to] == -1)
        {
          q.add(to);
          dist[to] = dist[v] + 1;
        }
    }
  }
   
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    n = con.nextInt();
    m = con.nextInt();
    s = con.nextInt();
    f = con.nextInt();
    
    g = new int[n+1][n+1];
    distS = new int[n+1];
    distF = new int[n+1];
    
    for (int i = 1; i <= m; i++)
    {
      int a = con.nextInt();
      int b = con.nextInt();
      g[a][b] = g[b][a] = 1;
    }

    bfs(s, distS);
    bfs(f, distF);
    
    int optDistance = distS[f];
    
    int res = 0;
    for(int i = 1; i <= n; i++)
    for (int j = i + 1; j <= n; j++)
      if (g[i][j] == 0)
      {
        if ((distS[i] + distF[j] + 1 >= optDistance) &&
            (distS[j] + distF[i] + 1 >= optDistance))
          res++;
      }

    System.out.println(res);
    con.close();
  }
}

Java