Дорога#6576

Дорога (Розбір)

Запустим алгоритм Крускала на вихідному графі. В множину $s$ додамо ребра, які входять в мінімальне остовне дерево. Далі перевіримо, чи належить задане ребро $(p, q)$ цьому остову. Для цього необхідно перевірити, чи міститься пара $(p, q)$ або $(q, p)$ в множині $s$ .

Приклад

Графи, наведені в прикладах, мають наступний вигляд:

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

Оголосимо структуру ребра графа, що містить пару вершин і вагу ребра. Оголосимо масив ребер $e$ .

struct Edge
{
  int u, v, dist;
};

vector<Edge> e;

Оголосимо масив $p a r e n t$ , що використовується для реалізації структури неперетинальних множин.

vector<int> parent;

Функція Repr знаходить представника множини, якому належить вершина $n$ .

int Repr(int n)
{
  while(n != parent[n]) n = parent[n];
  return n;
}

Функція Union об'єднує множини, що містять елементи $x$ і $y$ .

int Union(int x, int y)
{
  x = Repr(x); y = Repr(y);
  if (x == y) return 0;
  parent[y] = x;
  return 1;
}

C++

Функція lt служить компаратором для сортування ребер.

int lt(Edge a, Edge b)
{
  return (a.dist < b.dist);
}

Основна частина програми. Обробляємо декілька тестів.

scanf("%d", &tests);
while (tests--)
{

Читаємо вхідні дані. Ініціалізуємо масив $p a r e n t$ .

  scanf("%d %d %d %d", &n, &m, &p, &q);
  parent.resize(n + 1);
  for (i = 1; i <= n; i++) parent[i] = i;

Читаємо ребра графа.

  e.resize(m);
  for (i = 0; i < m; i++)
    scanf("%d %d %d", &e[i].u, &e[i].v, &e[i].dist);

Сортуємо ребра графа за зростанням ваги.

  sort(e.begin(), e.end(), lt);

При обробці кожного тесту обнуляємо змінну $f l a g$ . Вона приймає значення $1$ або $0$ залежно від того, чи належить ребро $(p, q)$ мінімальному остовному дереву.

  flag = 0;

Запускаємо алгоритм Крускала для побудови мінімального остову. Якщо ребро $(e [i] . u, e [i] . v)$ (e[i].u, e[i].v) включається в мінімальний остов, перевіряємо, чи співпадає воно з ребром $(p, q)$ .

  for (i = 0; i < m; i++)

    if (Union(e[i].u, e[i].v))

Необхідно перевірити дві умови: $(e [i] . u, e [i] . v) = (p, q)$ (e[i].u, e[i].v) = (p, q) і $(e [i] . u, e [i] . v) = (q, p)$ (e[i].u, e[i].v) = (q, p).

      if ((e[i].u == p && e[i].v == q) || 
          (e[i].u == q && e[i].v == p))
      {

Якщо ребро $(e [i] . u, e [i] . v)$ (e[i].u, e[i].v) співпадає з $(p, q)$ або $(q, p)$ , встановлюємо $f l a g = 1$ flag = 1 і виходимо з циклу.

        flag = 1;
        break;
      }

Залежно від значення змінної $f l a g$ виводимо відповідь.

  if (flag)
    puts("YES");
  else
    puts("NO");
}

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

Оголосимо структуру ребра графа, що містить пару вершин і вагу ребра. Оголосимо масив ребер $e$ .

struct Edge
{
  int u, v, dist;
};

vector<Edge> e;

Оголосимо масив $p a r e n t$ , що використовується для реалізації структури неперетинальних множин.

vector<int> parent;

У множині $s$ буде зберігатися ребра, що входять у мінімальне остовне дерево.

set<pair<int, int> > s;

Функція Repr знаходить представника множини, якому належить вершина $n$ .

int Repr(int n)
{
  while(n != parent[n]) n = parent[n];
  return n;
}

Функція Union об'єднує множини, що містять елементи $x$ і $y$ .

int Union(int x, int y)
{
  x = Repr(x); y = Repr(y);
  if (x == y) return 0;
  parent[y] = x;
  return 1;
}

C++

Функція lt служить компаратором для сортування ребер.

int lt(Edge a, Edge b)
{
  return (a.dist < b.dist);
}

Основна частина програми. Обробляємо декілька тестів.

scanf("%d", &tests);
while (tests--)
{

Читаємо вхідні дані. Ініціалізуємо масив $p a r e n t$ .

  scanf("%d %d %d %d", &n, &m, &p, &q);
  parent.resize(n + 1);
  for (i = 1; i <= n; i++) parent[i] = i;

Читаємо ребра графа.

  e.resize(m);
  for (i = 0; i < m; i++)
    scanf("%d %d %d", &e[i].u, &e[i].v, &e[i].dist);

Сортуємо ребра графа за зростанням ваги.

  sort(e.begin(), e.end(), lt);

При обробці кожного тесту очищаємо множину $s$ .

  s.clear();

Запускаємо алгоритм Крускала для побудови мінімального остовного дерева. Якщо ребро $(e [i] . u, e [i] . v)$ (e[i].u, e[i].v) включається в остов, додаємо його в множину $s$ .

  for (i = 0; i < m; i++)
    if (Union(e[i].u, e[i].v)) s.insert(make_pair(e[i].u, e[i].v));

Після завершення алгоритму перевіряємо, чи належить задане ребро $(p, q)$ мінімальному остову. Для цього потрібно з'ясувати, чи міститься пара $(p, q)$ або $(q, p)$ в множині $s$ .

  if ((s.find(make_pair(p, q)) != s.end()) ||
      (s.find(make_pair(q, p)) != s.end()))
    puts("YES");
  else
    puts("NO");
}

Java реалізація

import java.util.*;

class Edge
{
  int u, v, dist;
  Edge (int u, int v, int dist)
  {
    this.u = u;
    this.v = v;
    this.dist = dist;
  }
};

class Pair
{
  int u, v;
  Pair (int u, int v)
  {
    this.u = u;
    this.v = v;
  }
};

public class Main
{
  static int mas[];
  static int size[];
	
  static int Repr(int n)
  {
    if (n == mas[n]) return n;
    return mas[n] = Repr(mas[n]);
  }
	
  static int Union(int x, int y)
  {
    x = Repr(x); y = Repr(y);
    if(x == y) return 0;

    if (size[x] < size[y])
    {
      int temp = x; x = y; y = temp;
    }
    mas[y] = x;
    size[x] += size[y];
    return 1;
  }
  
  public static class MyFun implements Comparator<Edge>
  {
    public int compare(Edge a, Edge b)
    {
      return a.dist - b.dist;
    }
  }

  public static class PairFun implements Comparator<Pair>
  {
    public int compare(Pair a, Pair b)
    {
      if (a.u == b.u) return a.v - b.v;
      return a.u - b.u;
    }
  }
  
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    int tests = con.nextInt();
    while(tests-- > 0)
    {
      int n = con.nextInt();
      int m = con.nextInt();
      int p = con.nextInt();
      int q = con.nextInt();
      
      mas = new int[n+1];
      size = new int[n+1];
      for(int i = 1; i <= n; i++)
      {
        mas[i] = i;
        size[i] = 1;
      }

      Vector<Edge> v = new Vector<Edge>();
      for(int i = 0; i < m; i++)
      {
        int x = con.nextInt();
        int y = con.nextInt();
        int dist = con.nextInt();
        v.add(new Edge(x,y,dist));
      }

      Collections.sort(v, new MyFun());
    
      TreeSet<Pair> s = new TreeSet<Pair>(new PairFun());
      for(int i = 0; i < m; i++)
        if (Union(v.get(i).u,v.get(i).v) == 1) s.add(new Pair(v.get(i).u,v.get(i).v));
    
      if(s.contains(new Pair(p,q)) || s.contains(new Pair(q,p)))
        System.out.println("YES");
      else 
        System.out.println("NO");
    }
    con.close();
  }
}

Java