Bonjour,
J'essaye de résoudre ce problème http://www.spoj.com/problems/QUEST4/
J'ai essayé une approche gloutonne (prendre en premier les lignes/colonnes avec le plus de trous) mais cette approche est fausse.
Apparament il faut faire un couplage biparti https://fr.wikipedia.org/wiki/Couplage_(th%C3%A9orie_des_graphes)
mais je ne vois pas dans quel graphe le faire. J'imagine il faut construire un graphe biparti avec d'un côtés les sommets qui représentent les lignes/colonnes et de l'autre les trous. Mais ensuite ? Si on se contente de ça les couplages ne tiennent pas compte du fait qu'un trou est à la fois sur une ligne et sur une colonne.

Merci d'avance

Y'a un théorème (König) qui dit qu'un couplage maximal c'est la même chose qu'une couverture par sommets minimale, pour les graphes bipartis.
Pense avec la couverture par sommets ca devrait te sembler plus simple (tu veux minimiser le nombre de planches)