Yol#6576

Yol (Həll təhlili)

Kruskal alqoritmini başlanğıc qrafda işə salaq. $s$ çoxluğuna minimal ekran ağacına daxil olan qabığ təbəqələri əlavə edirik. Sonra verilmiş qabığın $(p, q)$ bu ağaca aid olub-olmadığını yoxlayırıq. Bunun üçün $(p, q)$ və ya $(q, p)$ cütlüyünün $s$ çoxluğunda olub-olmadığını yoxlamaq lazımdır.

Nümunə

Nümunələrdə verilən qraflar belə görünür:

Alqoritmin həyata keçirilməsi

Qrafın qabığını, zirvə cütlüyünü və qabığın çəkisini ehtiva edən strukturu elan edək. $e$ qabığının massivini elan edək.

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

vector<Edge> e;

Uygunsuz çoxluqlar strukturu üçün istifadə olunan $p a r e n t$ massivini elan edək.

vector<int> parent;

Repr funksiyası zirvənin $n$ aid olduğu çoxluğun nümayəndəsini tapır.

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

Union funksiyası $x$ və $y$ elementi ehtiva edən çoxluqları birləşdirir.

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

C++

lt funksiyası qabıqların sıralanmasına xidmət edir.

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

Proqramın əsas hissəsi. Çox sayda testlər emal edirik.

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

Giriş məlumatlarını oxuyuruq. $p a r e n t$ massivini inizializasiya edirik.

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

Qrafın qabıqlarını oxuyuruq.

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

Qrafın qabıqlarını çəkilərin artan sırasıyla sıralayırıq.

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

Hər testin işlənməsində $f l a g$ dəyişəni sıfırlayırıq. O, $(p, q)$ qabığa aid olub-olmadığını asılı olaraq $1$ və ya $0$ olur.

  flag = 0;

Minimal ekranı qurmaq üçün Kruskal alqoritmini işə salırıq. Əgər $(e [i] . u, e [i] . v)$ (e[i].u, e[i].v) qabığı minimal ekranın bir hissəsi olursa, bu qabığın $(p, q)$ ilə eyniliyini yoxlayırıq.

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

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

İki şərti yoxlamaq lazımdır: $(e [i] . u, e [i] . v) = (p, q)$ (e[i].u, e[i].v) = (p, q) və $(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))
      {

Əgər $(e [i] . u, e [i] . v)$ (e[i].u, e[i].v) qabığı $(p, q)$ və ya $(q, p)$ ilə eynidirsə, $f l a g = 1$ flag = 1 təyin edirik və dövrədən çıxırıq.

        flag = 1;
        break;
      }

$f l a g$ dəyişəninin dəyərinə bağlı olaraq, cavabı çıxarın.

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

Set - Alqoritm obrazı

Qrafın qabığını, zirvə cütlüyünü və qabığın çəkisini ehtiva edən strukturu elan edək. $e$ qabığının massivini elan edək.

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

vector<Edge> e;

Uygunsuz çoxluqlar strukturu üçün istifadə olunan $p a r e n t$ massivini elan edək.

vector<int> parent;

Minimal ekran ağacına daxil olan qabığları $s$ çoxluğunda saxlayaçıq.

set<pair<int, int> > s;

$R e p r$ funksiyası ilə, zirvənin $n$ aid olduğu çoxluğun nümayəndəsini tapırıq.

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

$U ni o n$ funksiyası ilə $x$ və $y$ cütləri olan çoxluqları birləşdiririk.

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

C++

lt funksiyası qabıqların sıralanmasına xidmət edir.

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

Proqramın əsas hissəsi və testlər çoxluğunun işlənməsi.

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

Giriş məlumatlarını oxuyuruq və $p a r e n t$ massivini inizializasiya edirik.

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

Qrafın qabıqlarını oxuyuruq.

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

Qrafın qabıqlarını çəkilərin artan sırasıyla sıralayırıq.

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

Hər testdən sonra $s$ çoxluğunu təmizləyirik.

  s.clear();

Minimal ostov qurmaq üçün Kruskal alqoritmini işə salırıq. Əgər $(e [i] . u, e [i] . v)$ (e[i].u, e[i].v) qabığı ostova daxil edilirsə, onu $s$ çoxluğuna əlavə edirik.

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

Alqoritm başa çatdıqdan sonra, verilmiş $(p, q)$ qabığının minimall ostova aid olub-olmadığını yoxlayırıq. Bunun üçün $(p, q)$ və ya $(q, p)$ çoxluğunda olub-olmadığını yoxlayırıq.

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

Java ilə həyata keçirilməsi

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