Şef və ikitərəfli qraf (Həll təhlili)

Həllin mövcudluq şərtlərinə baxaq. Qrafın hər hissəsində $n$ təpə yerləşir. Hər təpənin dərəcəsi $d$-dən az və $D$-dən çox olmamalı olduğuna görə, ümumi tillərin sayı $m$ aşağıdakı məhdudiyyətlərə cavab verməlidir:

Əgər bu şərt ödənmirsə, tələb olunan qrafı qurmaq mümkün deyil.

Qrafın qurulmasına keçək. Konstruktiv yanaşmadan istifadə edək. Sol hissənin təpələrini sağ hissənin təpələri ilə dövri sürüşmələr vasitəsilə birləşdirəcəyik.

1. cur = 0 dəyişənini işə salırıq.

2. Hər i~(1 \le i \le n) üçün sol hissənin $i$ təpəsi ilə sağ hissənin j = i + cur nömrəli təpəsi arasında til əlavə edirik. Əgər $j$ bündən çoxdursa, onda onun yerinə j = i + cur - n götürürük, yəni faktiki olaraq $n$ moduluna görə indeksasiyadan istifadə edirik. Hər til əlavə edildikdən sonra tillərin sayğacını artırırıq. Əlavə edilmiş tillərin ümumi sayı $m$-ə bərabər olan kimi, alqoritm başa çatır.

3. cur = cur + 1 artırırıq və $2$-ci addımı təkrarlayırıq.

Beləliklə, hər iterasiyada biz "sürüşdürülmüş" til dəstini əlavə edirik ki, bu da təpələrin dərəcələrinin bərabər paylanmasını təmin edir. Nəticədə hər təpənin dərəcəsi $D$-dən artıq olmur, kifayət qədər sayda iterasiyada isə ən azı $d$-yə çatır.

Misal

Misalda göstərilən qraf aşağıdakı görünüşə malikdir:

Alqoritmin realizasiyası

Testlərin sayı $tests$-i oxuyuruq.

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

Növbəti testin giriş məlumatlarını oxuyuruq.

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

Əgər zəruri bərabərsizliklərin ödənilməməsi səbəbindən qrafı qurmaq mümkün deyilsə, $-1$ çıxarırıq.

  if (n * d > m || n * D < m)
  {
    printf("-1\n");
    continue;
  }

cur = 0 təyin edirik.

  cur = 0;
  while (m > 0)
  {

Dəqiq $m$ til qurulana qədər, onları göstərilən alqoritmə görə qururuq.

    for (i = 1; i <= n; i++)
    {
      j = (i + cur) % n;
      if (j == 0) j = n;

$(i,j)$ tilini çıxarırıq.

      printf("%d %d\n", i, j);
      m--;

Bütün $m$ til qurulan kimi, proqramı başa çatdırırıq.

      if (m == 0) break;
    }

$cur$ dəyişəninin qiymətini $1$ artırırıq.

    cur++;
  }
}