Lo Chef e il grafo bipartito (Editoriale)

Consideriamo le condizioni di esistenza della soluzione. In ciascuna parte del grafo si trovano $n$ vertici. Poiché il grado di ogni vertice deve essere non minore di $d$ e non maggiore di $D$, il numero totale di archi $m$ deve soddisfare le seguenti restrizioni:

Se questa condizione non è soddisfatta, è impossibile costruire il grafo richiesto.

Passiamo alla costruzione del grafo. Utilizziamo un approccio costruttivo. Collegheremo i vertici della parte sinistra con i vertici della parte destra mediante spostamenti ciclici.

1. Inizializziamo la variabile cur = 0.

2. Per ogni i~(1 \le i \le n) aggiungiamo un arco tra il vertice $i$ della parte sinistra e il vertice della parte destra con numero j = i + cur. Se j \gt n, allora al suo posto prendiamo j = i + cur - n, cioè in pratica usiamo l'indicizzazione modulo $n$. Dopo aver aggiunto ogni arco, incrementiamo il contatore degli archi. Non appena il numero totale di archi aggiunti diventa uguale a $m$, l'algoritmo termina.

3. Incrementiamo cur = cur + 1 e ripetiamo il passo $2$.

In questo modo, a ogni iterazione aggiungiamo un insieme "spostato" di archi, il che garantisce una distribuzione uniforme dei gradi dei vertici. Come risultato, il grado di ogni vertice non supera $D$, e con un numero sufficiente di iterazioni raggiunge almeno $d$.

Esempio

Il grafo riportato nell'esempio ha il seguente aspetto:

Implementazione dell'algoritmo

Leggiamo il numero di test $tests$.

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

Leggiamo i dati in ingresso del test successivo.

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

Se il grafo non può essere costruito a causa della non soddisfazione delle disuguaglianze necessarie, stampiamo $-1$.

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

Impostiamo cur = 0.

  cur = 0;
  while (m > 0)
  {

Finché non saranno costruiti esattamente $m$ archi, li costruiamo secondo l'algoritmo indicato.

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

Stampiamo l'arco $(i,j)$.

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

Non appena tutti gli $m$ archi saranno costruiti, terminiamo il programma.

      if (m == 0) break;
    }

Incrementiamo di $1$ il valore della variabile $cur$.

    cur++;
  }
}