Rezolvare completă PbInfo #1497 Nunta

La o nuntă sunt invitate n persoane, numerotate de la 1 la n. Se știe că o parte din ele se cunosc două câte două, fie că sunt rude, fie de la serviciu, fie sunt prieteni sau vecini. Astfel se vor forma un număr K minim de grupuri astfel încât în fiecare grup, fiecare persoană să aibă cel puţin un cunoscut. Pentru fiecare grup de cel puțin două persoane se stabileşte un lider – persoana cu numărul de ordine minim. Aceste grupuri vor fi numerotate de la 1 la K în ordinea crescătoare a numerelor de ordine ale liderilor. Ca sa se ivească cât mai puține situații stânjenitoare, organizatorul nunții ar dori să aranjeze o masă principală cu cel puţin n/2+1 invitaţi, la care să fie aşezate unul sau mai multe astfel de grupuri întregi numerotate cu valori consecutive.

Cerința

Fiind date n, numărul de persoane, m, numărul de perechi de invitaţi care se cunosc între ei și cele m perechi, să se determine numărul K minim de grupuri formate din cel puțin doi invitați astfel încât, în fiecare grup, fiecare persoană să aibă cel puţin un cunoscut, precum şi numărul variantelor distincte în care se poate organiza masa cu cel puţin n/2+1 invitaţi din grupurile formate.

Date de intrare

Fișierul de intrare nunta.in conține pe prima linie două numere naturale separate prin spațiu n și m, n reprezentând numărul de invitaţi, respectiv m numărul de perechi de invitaţi care se cunosc între ei. Pe fiecare din următoarele m linii se află câte două numere naturale x și y, 1≤x, y≤n, separate printr-un spațiu, cu semnificația că invitaţii x și y se cunosc între ei.

Date de ieșire

Fișierul de ieșire nunta.out va conține pe prima linie un număr natural g reprezentând numărul minim de grupuri formate din cel puțin doi invitați astfel încât, în fiecare grup, fiecare persoană să aibă cel puţin un cunoscut. Pe cea de a doua linie va fi scris un număr natural v reprezentând numărul variantelor distincte în care se poate organiza masa cu cel puţin n/2+1 invitaţi din grupurile formate.

Restricții și precizări

  • 0 < n <= 20000
  • 0 < m <= 100000

Exemplul 1

nunta.in

31 6
5 7
2 3
10 14
14 6
9 15
7 30

nunta.out

4
0

Explicație

Grupurile formate din cel puțin doi invitați sunt : (2,3), (5,7,30), (6,10,14), (9,15), deci K=4. Ele nu sunt suficiente pentru a forma o masă cu cel puţin 16 invitaţi, deci sunt 0 variante de aranjare.

Exemplul 2

nunta.in

12 8
1 2
6 5
3 2
10 8
3 4
7 8
1 4
12 9

nunta.out

4
3

Explicație

Sunt k=4 grupuri formate din cel puțin doi invitați. Acestea sunt: G1=(1,2,3,4), G2=(5,6), G3=(7,8,10), G4=(9,12).

Variantele distincte în care se poate organiza masa cu cel puţin n/2+1, adică 7 invitaţi din grupurile formate sunt: G1+G2+G3, G1+G2+G3+G4 și G2+G3+G4. G1+G3+G4 nu este alcătuit din grupuri numerotate cu valori consecutive.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Nunta:

#include <iostream>
#include <fstream>


using namespace std;

struct nod
{int inf;
 nod *leg;
} *L[20001];

ifstream f("nunta.in");
ofstream g("nunta.out");
int n,m,viz[20001],v[20001],k,nr,var,s;

void adaug(int x, int y)
{
    nod *c;
    c=new nod;
    c->inf=y;
    c->leg=L[x];
    L[x]=c;
}

void citire()
{
    int i,x,y;
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y;
        adaug(x,y);
        adaug(y,x);
    }
    f.close();
}

void DF(int i)
{
    nod *c;
    viz[i]=1;
    //cout<<i<<' ';
    nr++;
    for (c=L[i];c;c=c->leg)
        if (!viz[c->inf]) DF(c->inf);
}

int main()
{   int i,j;
    citire();

    for (i=1;i<=n;i++)
        if(!viz[i])
    {
        nr=0;
        DF(i);
        //cout<<'\n';
        if (nr>=2) v[++k]=nr;
    }
    g<<k<<'\n';
   /* for (i=1;i<=k ;i++) cout <<v[i]<<" ";
    cout<<endl;
    */
    s=0; //numarul de invitati din grupurile selectate
    var=0; // numarul de variante de aranjare a mesei cu cel putin n/2+1 invitati
    i=0; // indicele grupului curent
    while (s<=n/2 && i<=k) s+=v[++i];  // prima varianta posibila
    var+=k-i+1; // se aduna numarul de variante care incep cu v[1]
    j=1;
    while (i<=k)
     {
         s-=v[j];
         while (s<=n/2 && i<=k) s+=v[++i];
         var+=k-i+1; //se aduna numarul variantelor care incep cu V[j+1]
         j++;
     }
    g<<var;

    g.close();
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email.

Rezolvarea problemei #1497 Nunta

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1497 Nunta de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!