Транспортна Система#9635

Транспортна Система (Розбір)

Давайте запустимо пошук у ширину, починаючи з вихідної вершини $s$ та кінцевої вершини $f$ . Збережемо найкоротші відстані від $s$ в масив $d i s tS$ і від $f$ в масив $d i s tF$ .

Нехай $o pt D i s t an ce$ optDistance позначає найкоротшу відстань між $s$ і $f$ в оригінальному графі.

Тепер розглянемо можливість побудови нової дороги між вершинами $i$ і $j$ .

При додаванні дороги $(i, j)$ до графу створюються нові шляхи:

s \to i \to j \to f w i t h l e n g t h d i s tS [i] + 1 + d i s tF [j], s \to j \to i \to f w i t h l e n g t h d i s tS [j] + 1 + d i s tF [i]

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

Якщо хоча б одна з цих відстаней менша за $o pt D i s t an ce$ optDistance, то додавання дороги $(i, j)$ зменшить найкоротшу відстань між $s$ і $f$ , і таким чином вона не підходить.

Тепер нам потрібно перевірити всі можливі пари $(i, j)$ і перевірити, чи зменшить будівництво нової дороги найкоротшу відстань між $s$ і $f$ .

Приклад

Граф з першого тесту показаний зліва. Найкоротша відстань від вершини $1$ до вершини $5$ становить $4$ . Незалежно від того, яку нову дорогу ми додамо, ця відстань зменшиться. Тому жодна з необхідних доріг не існує.

Граф з другого тесту показаний праворуч. Найкоротша відстань від вершини $3$ до вершини $5$ становить $2$ . Можливі нові дороги позначені жирними лініями. Незалежно від того, яку з цих доріг ми побудуємо, відстань між $3$ і $5$ не зменшиться.

Реалізація алгоритму

Визначимо константу $M A X$ — максимальну можливу кількість вершин у графі.

#define MAX 1001

Оголосимо матрицю суміжності $g$ та масиви для найкоротших відстаней.

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

Функція bfs виконує пошук у ширину від вершини $s t a r t$ . Вона приймає масив $d i s t$ як вхідні дані, де будуть збережені найкоротші відстані.

void bfs(int start, int *dist)
{

Ініціалізуємо масив найкоротших відстаней $d i s t$ .

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

Оголосимо чергу $q$ і додамо до неї початкову вершину $s t a r t$ .

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

Поки черга не порожня, беремо вершину $v$ з черги.

  while (!q.empty())
  {

    int v = q.front(); q.pop();

Обходимо всі вершини $t o$ , суміжні з $v$ . Якщо вершина $t o$ ще не відвідана, обчислюємо найкоротшу відстань $d i s t [t o]$ dist[to] і додаємо її до черги.

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

C++

Основна частина програми. Зчитуємо вхідні дані.

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

Зчитуємо неорієнтований граф.

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

Запускаємо пошук у ширину від вершин $s$ та $f$ . Найкоротші відстані зберігаються у масивах $d i s tS$ та $d i s tF$ відповідно.

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

Нехай $o pt D i s t an ce$ optDistance позначає найкоротшу відстань між $s$ і $f$ в оригінальному графі.

optDistance = distS[f];

Обходимо всі пари вершин $i$ та $j$ і розглядаємо можливість побудови нової дороги між ними. Змінна $r es$ відстежує кількість таких допустимих доріг.

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

Якщо між вершинами $i$ та $j$ немає дороги, обчислюємо довжини найкоротших шляхів: $s \to i \to j \to f$ s → i → j → f та $s \to j \to i \to f$ s → j → i → f. Якщо обидві ці відстані не менші за $o pt D i s t an ce$ optDistance, тоді побудова такої дороги дозволена.

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

Виводимо відповідь.

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

Реалізація на Java

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