Recherche:

Les défis ne se ferment jamais :aie:

Pour l'instant, il n'y a pas eu de solution complète sans erreurs (sauf la brute-force) (EDIT : ah si, celle de dividee doit être bonne ;) )

Et il y a...

En fait, dès que le graphe est faiblement connexe, il y a une méthode vachement plus simple que de passer par des flots.

Donc, peut être que ta méthode est bonne (il y a peut être des contre...

Je comprenais pas pourquoi tu faisais :



Là, on aurait dît que tu reliais la source aux sommets qui sont des puits.


Et pour le coût, c'est juste que je n'ai jamais entendu parlé de coût...

Je ne comprend pas ce que tu appelles un coût ?
A quoi sert-il ?

Je vois bien ce qu'est une coupe, mais ce n'est pas un entier mais un ensemble de couple de sommets. Une coupe peut avoir une...

Je ne suis pas toujours convaincu que ça marche.

Tu peux dérouler ton algo sur mon exemple ?

Si tu choisis mal ton puit et ta source, le calcul de flot maximal ne pourra amener à rien sur mon...

Oui, quand je dis marche, ça veut dire optimal ^^ (puisque c'est le but du défi).




Courage :mrgreen:

@cleth :
Je suis pas sûr que ta méthode marche

Sur le graphe :

http://humbert-florent.developpez.com/images/forum/defi5/graphe5.gif

Tu peux te retrouver à prendre une source A et le puit...

@bredelet : Tu peux donner le principe général de ton algo ?

Notamment avec des mots comme : On détermine les composantes fortements connexes, on calcule les puits et les sources etc.

Tu as raison, si on relit les puits aux sources n'importe comment quand le graphe est faiblement connexe. Cela ne marche pas.
Donc s'il n'y a pas de règles spéciales pour le cas là, ton programme ne...

Si c'était le seul principe, mon contre exemple est le suivant :

Graphe de 3 sommets, (A,B,C) et un seul arc (A,B)

Tu peux choisir A comme ayant un degré entrant de 0 et B comme ayant un degré...

Avec ça, je suis OK :



Mais la ligne du dessus ne suffisait pas tout seul ;)

Mais pourquoi est-ce le nombre minimal ?

Comment ça sous réserve que le graphe des CFC résultant est connexe ?

Bah, si t'as un graphe non fortement connexe et que t'ajoutes un arc et qu'il est fortement connexe, c'est que ça va :aie:

Si ceci est ton principe. Cela ne marche pas à tous les coups ;)

Bonjour,

Pour ce cinquième défi, l'équipe de developpez.com vous propose un challenge un peu plus difficile.

Le problème est composé de 2 problèmes assez proches. Vous pouvez donc proposer une...