Ah oui, exact. C'est du cut/flow sur les plaques et pas sur les trous. Bien joué !
Du coup, ca explique l'indication.
Ah oui, exact. C'est du cut/flow sur les plaques et pas sur les trous. Bien joué !
Du coup, ca explique l'indication.
ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.
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.
« La science informatique n'est pas plus la science des ordinateurs que l'astronomie n'est celle des télescopes. » — Edsger Dijkstra
Merci a vous tous pour votre aide
Merci beacoup
Haaa je viens de comprendre 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.
« La science informatique n'est pas plus la science des ordinateurs que l'astronomie n'est celle des télescopes. » — Edsger Dijkstra
ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.
Vous avez un bloqueur de publicités installé.
Le Club Developpez.com n'affiche que des publicités IT, discrètes et non intrusives.
Afin que nous puissions continuer à vous fournir gratuitement du contenu de qualité, merci de nous soutenir en désactivant votre bloqueur de publicités sur Developpez.com.
Partager