Ah oui, exact. C'est du cut/flow sur les plaques et pas sur les trous. Bien joué ! :ccool:Citation:
Envoyé par hellfoust
Du coup, ca explique l'indication. :D
Version imprimable
Ah oui, exact. C'est du cut/flow sur les plaques et pas sur les trous. Bien joué ! :ccool:Citation:
Envoyé par hellfoust
Du coup, ca explique l'indication. :D
Peux etre il faut transformer le graphe biparti en reseau de transport puis voir le flux maximal ?
A mon sens le graphe biparti correspondant au problème est le graphe ayant pour noeuds : un noeud par trou de la matrice et un noeud par droite, et ayant pour arcs : un arc entre un "trou" et une "droite" (au plus 2) à laquelle il participe (cf ma première réponse a propos du set cover). Mais je n'ai pas réussi à trouver ce qui fait que ce cas est plus simple que le cas général.
Merci a vous tous pour votre aide :ccool:
Merci beacoup :)
Haaa je viens de comprendre :P Pour ceux qui sont lents comme moi : les solutions proposées jusqu'à présent n'exploitaient pas le fait que :
- une droite verticale ne peut couper qu'une droite horizontale (d'où le fait que le graphe soit biparti)
- une case est défini par une ligne et par une colonne (d'où la possibilité de representer les cases sous la forme d'arc)
La solution de hellfoust exploite ces deux propriétés. Bien vue :).
J'aurai juste une remarque (il faut bien que j'en ai une) : penser à traiter le cas des plaques obligatoires (il n'y a pas d'arcs pour les cases n'appartenant pas à une intersection, elles ne sont donc pas prises en compte lors de la recherche du vertex cover) et ne pas les faire figurer dans le graphe.
Je penses que toutes les cases peuvent être couvertes par deux plaques (une verticale et une horizontale). Pour les cases "obligatoires", l'une des deux plaques est de taille "1".Citation:
Envoyé par Acrim
Tu as raison. J'étais à coté de la plaque. Donc plus de remarques :).Citation:
Envoyé par pseudocode