Joc cooperatiu P74845


Statement
 

pdf   zip

thehtml

Les competicions ja no estan de moda. El que es porta ara són els jocs cooperatius, en què els participants col·laboren per assolir un objectiu comú. Així, un grup de n amics s’inspira en el joc de la cadena, en què una fila de persones es diuen a cau d’orella un missatge M d’una punta a l’altra, amb l’objectiu que M no es corrompi pel camí. No obstant, per fer el joc més divertit, s’hi introdueix algun canvi:

Sigui x l’emissor inicial de M, i sigui y el receptor final. A cada ronda del joc, la persona ‍u que acaba de rebre M (o bé x, si és la primera ronda) ha d’escollir una altra persona v i transmetre-li M. Per a tot parell (u, v), es coneix la probabilitat puv de que la transmissió directa del missatge de u a v sigui correcta. Aquesta probabilitat és independent de la ronda. Un missatge corromput no es recupera mai. El joc acaba quan M arriba a y.

Jugant òptimament, quina és la probabilitat de que M es transmeti de x a y correctament?

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb el nombre d’amics n i el nombre m de probabilitats puv que són estrictament positives. Segueixen m tripletes u, v, puv, on uv. Finalment, tenim x i y. Assumiu 1 ≤ n ≤ 104, 0 ≤ m ≤ 5n, i que cada parell de u i v apareix com a molt un cop a l’entrada. Els amics estan numerats entre 0 i n−1.

Sortida

Per cada cas, escriviu amb cinc dígits decimals la màxima probabilitat de que el missatge arribi correctament de x a y. Si és impossible, digueu-ho.

Pista

La solució esperada està basada en un algorisme fonamental sobre els grafs.

Public test cases
  • Input

    6 8
    1 0 0.02478
    3 4 0.49787
    3 1 0.00335
    0 5 0.06737
    0 2 0.76787
    5 1 0.00045
    4 1 0.93533
    2 3 0.18315
    3 5
    
    2 1
    0 1 1
    1 0
    
    1 0
    0 0
    
    3 4
    2 0 0.75008
    0 2 0.00004
    0 1 0.01831
    1 2 0.00091
    0 2
    

    Output

    0.00078
    impossible
    1.00000
    0.00004
    
  • Information
    Author
    Enric Rodríguez
    Language
    Catalan
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++