3508 - Bal

From Bitnami MediaWiki
Revision as of 12:34, 12 December 2023 by Mesarosdenisa (talk | contribs) (Pagină nouă: == Cerinta == La balul din acest an participă n băieți și n fete, numerotați de la 1 la n. Compatibilitățile dintre aceștia pot fi reprezentate sub forma unui graf bipartit. Fie mat matricea de adiacentă. Atunci, băiatul i se poate cupla cu fata j doar dacă sunt compatibili, adică mat[i][j] = 1. Aflați numărul de moduri de a forma cele n cupluri. == Date de intrare == Programul citește de la tastatură numărul n, iar apoi matricea de adiacență. == Date d...)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Cerinta

La balul din acest an participă n băieți și n fete, numerotați de la 1 la n. Compatibilitățile dintre aceștia pot fi reprezentate sub forma unui graf bipartit. Fie mat matricea de adiacentă. Atunci, băiatul i se poate cupla cu fata j doar dacă sunt compatibili, adică mat[i][j] = 1. Aflați numărul de moduri de a forma cele n cupluri.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi matricea de adiacență.

Date de iesire

Programul va afișa pe ecran numărul de moduri de a forma cuplurile, modulo 1.000.000.007.

Restrictii si precizari

  • 1 < n < 25

Exemplul 1

Intrare
3
0 1 1
1 0 1
1 1 1
Iesire
Datele introduse corespund restrictiilor impuse
3

Exemplul 2

Intrare
3
-5 34 0
3 87 0
0 0 -1
Iesire
Datele introduse nu corespund restrictiilor impuse


Rezolvare

<syntaxhighlight lang="python3" line="1"> def numara_cupluri(mat, n):

   MOD = 1000000007
   def dfs(baiat, vazut):
       vazut[baiat] = True
       for fata in range(n):
           if mat[baiat][fata] and not vazut[n + fata]:
               vazut[n + fata] = True
               if perechi[n + fata] == -1 or dfs(perechi[n + fata], vazut):
                   perechi[n + fata] = baiat
                   return True
       return False
   perechi = [-1] * (2 * n)
   rezultat = 0
   for baiat in range(n):
       vazut = [False] * (2 * n)
       if dfs(baiat, vazut):
           rezultat += 1
   return rezultat % MOD
  1. Citire număr de băieți/fete și matricea de adiacență

n = int(input("Introduceți numărul n: ")) matrice_adiacenta = [list(map(int, input().split())) for _ in range(n)]

  1. Calcul și afișare rezultat

rezultat = numara_cupluri(matrice_adiacenta, n) print(rezultat) </syntaxhighlight>

Explicatie

Cele 3 modalități sunt:

(1, 2), (2, 1), (3, 3)
(1, 2), (2, 3), (3, 1)
(1, 3), (2, 1), (3, 2)