Flot maximum

Définition

On cherche à acheminer la plus grande quantité possible de ressources d'une source S vers un puits T dans un réseau.

Principe

L'idée initiale de chercher un chemin positif de S à T et d'y augmenter le flot est incomplète. On ajoute des arcs résiduels (arcs retour) pour permettre des annulations partielles, un mécanisme de révision. Le flot résiduel initial est nul.

Tous les poids mentionnés dans la suite correspondent à des capacités résiduelles.

Implémentation

Méthodes EK/FF

Utilisent un parcours en largeur (BFS) ou en profondeur (DFS) de manière brute.

Algorithme ISAP

Calcule les distances dans le graphe résiduel inversé (pratique mais non strictement nécessaire) pour créer une stratification. Un DFS est ensuite utilisé pour distribuer le nouveau flot selon ces niveaux.

Des optimisations classiques s'appliquent : l'optimisation du gap, la heuristique de l'arc courant. Pour des graphes peu profonds, une approche empirique peut réduire le nombre d'itérations.

namespace flot_max {
    const int MAX_ND = 1e5 + 10, MAX_AR = 2e5 + 10;
    int debut[MAX_ND], suivant[MAX_AR], destination[MAX_AR], capacite[MAX_AR];
    int compteur_aretes = 1, source, puits, nb_noeuds;
    int compteur_niveaux[MAX_ND], distance[MAX_ND], arc_courant[MAX_ND];

    inline void creer_arc(int depart, int arrivee, int capac) {
        suivant[++compteur_aretes] = debut[depart];
        debut[depart] = compteur_aretes;
        destination[compteur_aretes] = arrivee;
        capacite[compteur_aretes] = capac;
    }

    inline void ajouter_arc(int u, int v, int cap) {
        creer_arc(u, v, cap);
        creer_arc(v, u, 0);
    }

    inline int recherche_augmentation(int noeud, int flot_entrant) {
        if (noeud == puits) return flot_entrant;

        int flot_sortant = 0;
        for (int &arete = arc_courant[noeud]; arete; arete = suivant[arete]) {
            int voisin = destination[arete];
            if (capacite[arete] <= 0 || distance[noeud] != distance[voisin] + 1) continue;

            int flot_transmis = recherche_augmentation(voisin, std::min(capacite[arete], flot_entrant - flot_sortant));
            capacite[arete] -= flot_transmis;
            capacite[arete ^ 1] += flot_transmis;
            flot_sortant += flot_transmis;

            if (flot_sortant == flot_entrant || distance[source] >= nb_noeuds) return flot_sortant;
        }

        if (--compteur_niveaux[distance[noeud]] == 0) distance[source] = nb_noeuds;
        ++compteur_niveaux[++distance[noeud]];
        arc_courant[noeud] = debut[noeud];
        return flot_sortant;
    }

    inline int calculer_flot_max() {
        int flot_total = 0;
        for (int i = 1; i <= nb_noeuds; ++i) arc_courant[i] = debut[i];
        while (distance[source] < nb_noeuds) {
            flot_total += recherche_augmentation(source, INT_MAX);
        }
        return flot_total;
    }
}

Points d'attention

• Dans une liste d'adjacence (forward star), les arcs directs et retour doivent être créés consécutivement.
• L'index compteur_aretes doit commencer à une valeur impaire (ex: 1).
• Pour les graphes en grille, l'utilisation d'un tableau id[ligne][colonne] nécessite une attention particulière. Il est préférable de structurer le code en sections claires.
• Bien dimensionner les tableaux en fonction des contraintes du problème.

Modélisation

• Identifier par intuition ou analyse la structure du graphe sous-jacent.
• Faire le lien avec les états d'une programmation dynamique.
• Utiliser des nœuds pour distribuer des flux.
• Découper le graphe en niveaux et utiliser le réseau résiduel jusqu'à ce que le flot atteigne un seuil (EK/Dinic peut être plus adapté ici).
• Convertir le problème en coupe minimum, souvent résoluble par programmation dynamique.

Coupe minimum

Définition

Partitionner les nœuds du réseau en deux ensembles contenant respectivement S et T, de manière à minimiser la somme des capacités des arcs allant de l'ensemble contenant S vers celui contenant T.

Principe

La valeur de la coupe minimum est égale au flot maximum. Cela découle du théorème flot-max/coupe-min : un flot non maximum impliquerait l'existence d'un chemin augmentant non saturé.

Implémentation

Identique à celle du flot maximum.

Modélisation

• L'idée centrale est d'interdire tout chemin reliant S à T dans la coupe.
• Pour les graphes en grille, un coloriage (2 ou 4 couleurs) peut orienter la construction du réseau. Mais ce n'est pas une règle absolue.
• Les arcs en série modélisent une condition "OU". Les arcs en parallèle modélisent une condition "ET".
• Transformer des poids sur les nœuds en poids sur les arcs (technique de découpage des nœuds).
• Appliquer des limites sur les flux entrants/sortants d'un nœud.
• Attribuer un coût aux nœuds en fonction de leur type.
• Attribuer un coût supplémentaire à un groupe de nœuds (la modélisation est similaire au point suivant).
• Attribuer un gain aux nœuds en fonction de leur type.
• Attribuer un gain supplémentaire à un groupe de nœuds (par exemple, la présence d'un gain implique qu'aucun nœud du groupe ne peut être connecté au puits T).
• Lorsque l'appartenance à un même ensemble a un coût, on peut choisir d'inverser le sens de certains chemins ou d'échanger les poids des arcs entre ensembles.
• Pour trouver une coupe minimum avec un nombre minimal d'arc coupés, on peut utiliser une méthode incrémentale (ex: multiplier les capacités originales par un grand facteur et ajouter 1).

Problème de la fermeture de poids maximum

Définition

Trouver un ensemble de nœuds sans arcs sortants (fermé) dont la somme des poids est maximale.

Principe

La solution est Somme_des_poids_positifs - Valeur_de_la_coupe_minimum. Exclure un nœud de poids positif a un coût. Inclure un nœud de poids négatif a également un coût.

Implémentation

Sur le graphe original, connecter la source S à chaque nœud de poids positif avec une capacité égale à son poids. Connecter chaque nœud de poids négatif au puits T avec une capacité égale à l'opposé de son poids.

Modélisation

• Applicable lorsque des relations de dépendance pondérées claires existent.
• Dans un graphe biparti, pour imposer l'égalité des flux des deux côtés, on peut ajouter une capacité infinie d'un côté et en soustraire de l'autre. Une autre technique est l'échelle et la compression d'information.

Flot à coût minimum

Définition

Chercher un flot réalisable de valeur maximale (ou imposée) dont le coût total (somme des coûts des arcs utilisés multipliés par le flot qui y passe) est minimum.

Principe

Stratégie gloutonne : augmenter toujours le long du chemin le plus court (au sens du coût) dans le graphe résiduel. C'est une généralisation de l'algorithme de plus court chemin dans ISAP.

Implémentation

Utiliser SPFA (Shortest Path Faster Algorithm) pour trouver le plus court chemin (tolérant les cycles négatifs, parcourant seulement les arcs avec une capacité résiduelle positive), puis augmenter le flot le long de ce chemin.

Le multi-flux (chemins disjoints) peut être utilisé.

Une approche similaire à SAP est possible, mais sans les mêmes optimisations.

Détails techniques

Lors de l'utilisation d'un tableau comme file statique, vérifier systématiquement les dépassements d'indice et gérer la réutilisation cyclique de la mémoire.

Pour memset, privilégier l'opérateur sizeof plutôt qu'un calcul manuel. Dimensionner les tableaux de nœuds avec précision. (Note de développeur)

Il est possible d'ajouter des arcs dynamiquement au réseau.

Modélisation

Le flot maximum satisfait une contrainte, le coût minimum optimise un second objectif.

Technique de découpage de nœuds pour imposer un flot

Découper un nœud en deux est souvent nécessaire, mais il est difficile d'imposer exactement un flot donné sur ce nœud. Une approche consiste à faire en sorte que les 2n nœuds résultants acquièrent un flot "ab initio" (avec un coût), puis à redistribuer ce flot selon les contraintes du problème. Cette "redistribution" obéit à un ordre partiel ; les nœuds d'un même niveau peuvent aussi avoir des relations d'ordre partiel.

Exemple supplémentaire

Technique de découpage de nœuds avec orientation

Dans un graphe en grille, seuls les virages formant une boucle ont une valeur. Par coloriage et classsification, on sépare pour un nœud ses directions verticale et horizontale. Deux arcs sont créés : l'un avec coût, l'autre sans. Le coût final est la somme des coûts des arcs utilisés moins une fois la somme des coûts de base. Les nœuds adjacents sont connectés selon ces directions correspondantes.

On peut calculer une valeur globale et en soustraire une partie. Pré-définir certains états, puis les ajuster.

Découpage des valeurs absolues.

Flots en réseaux avec bornes

Définition

Chaque arc (u, v) possède une borne inférieure l(u, v) et une borne supérieure c(u, v) pour le flot qui le traverse.

Flot réalisable

Déterminer s'il existe un flot satisfaisant toutes les bornes.

Flot maximum / minimum sous contraintes

Trouver le flot de valeur maximale (ou minimale) qui respecte toutes les bornes.

Implémentation

namespace flot_bornes {
    const int MAX_ND = 1e5 + 10, MAX_AR = 2e6 + 10;
    int source_originale, puits_originale;
    int source_aux, puits_aux;
    int source_2, puits_2;
    int nb_noeuds;
    int debut[MAX_ND], suivant[MAX_AR], destination[MAX_AR], capacite_residuelle[MAX_AR];
    int compteur_aretes = 1, arc_courant[MAX_ND], compteur_niveaux[MAX_ND], distance[MAX_ND];
    int excedent_flot, degre[MAX_ND];

    inline void creer_arc(int depart, int arrivee, int capac) {
        suivant[++compteur_aretes] = debut[depart];
        debut[depart] = compteur_aretes;
        destination[compteur_aretes] = arrivee;
        capacite_residuelle[compteur_aretes] = capac;
    }

    inline void ajouter_arc_contraint(int u, int v, int borne_inf, int borne_sup) {
        degre[v] += borne_inf;
        degre[u] -= borne_inf;
        creer_arc(u, v, borne_sup - borne_inf);
        creer_arc(v, u, 0);
    }

    inline int recherche_augmentation(int noeud, int flot_entrant) {
        if (noeud == puits_2) return flot_entrant;

        int flot_sortant = 0;
        for (int &arete = arc_courant[noeud]; arete; arete = suivant[arete]) {
            int voisin = destination[arete];
            if (capacite_residuelle[arete] <= 0 || distance[noeud] != distance[voisin] + 1) continue;

            int flot_transmis = recherche_augmentation(voisin, std::min(capacite_residuelle[arete], flot_entrant - flot_sortant));
            capacite_residuelle[arete] -= flot_transmis;
            capacite_residuelle[arete ^ 1] += flot_transmis;
            flot_sortant += flot_transmis;

            if (flot_sortant == flot_entrant || distance[source_2] >= nb_noeuds) return flot_sortant;
        }

        if (--compteur_niveaux[distance[noeud]] == 0) distance[source_2] = nb_noeuds;
        ++compteur_niveaux[++distance[noeud]];
        arc_courant[noeud] = debut[noeud];
        return flot_sortant;
    }

    inline void reinitialiser_distances() {
        memset(distance, 0, sizeof distance);
        memset(compteur_niveaux, 0, sizeof compteur_niveaux);
    }

    inline int resoudre() {
        // Ajouter l'arc reliant le puits à la source pour contrôler la valeur du flot
        creer_arc(puits_originale, source_originale, INT_MAX);
        creer_arc(source_originale, puits_originale, 0);
        int arete_flot_total = compteur_aretes; // Garder une référence à cet arc

        // Construire le réseau auxiliaire pour le flot réalisable
        for (int i = 1; i <= nb_noeuds; ++i) {
            if (degre[i] > 0) {
                creer_arc(source_aux, i, degre[i]);
                creer_arc(i, source_aux, 0);
                excedent_flot += degre[i];
            } else if (degre[i] < 0) {
                creer_arc(i, puits_aux, -degre[i]);
                creer_arc(puits_aux, i, 0);
            }
        }

        // Initialiser pour le premier problème (flot réalisable)
        for (int i = 1; i <= nb_noeuds; ++i) arc_courant[i] = debut[i];
        int flot_realise = 0;
        source_2 = source_aux;
        puits_2 = puits_aux;
        while (distance[source_2] < nb_noeuds) {
            flot_realise += recherche_augmentation(source_2, INT_MAX);
        }

        if (flot_realise != excedent_flot) return -1; // Pas de solution réalisable

        reinitialiser_distances();

        // Initialiser pour le second problème (flot max/min dans l'arc (puits, source))
        for (int i = 1; i <= nb_noeuds; ++i) arc_courant[i] = debut[i];
        source_2 = source_originale;
        puits_2 = puits_originale;
        // Récupérer la valeur de base du flot dans l'arc ajouté et le neutraliser
        int valeur_flot_base = capacite_residuelle[arete_flot_total];
        capacite_residuelle[arete_flot_total] = 0;
        capacite_residuelle[arete_flot_total ^ 1] = 0;

        int valeur_flot_final = valeur_flot_base;
        while (distance[source_2] < nb_noeuds) {
            valeur_flot_final += recherche_augmentation(source_2, INT_MAX);
        }
        return valeur_flot_final;
    }
}

Flot à coût minimum sous bornes

Définition

Il faut distinguer le flot à coût minimum de valeur maximum du simple flot à coût minimum. Pour ce dernier, on peut s'arrêter dès que le coût du chemin augmentant trouvé n'est plus avantageux.

Implémentation

namespace cout_min_bornes {
    const int MAX_ND = 1e5 + 10, MAX_AR = 2e6 + 10;
    int source_originale, puits_originale, source_aux, puits_aux, source_2, puits_2, nb_noeuds;
    int debut[MAX_ND], suivant[MAX_AR], destination[MAX_AR], capacite[MAX_AR], cout[MAX_AR];
    int compteur_aretes = 1, file[MAX_ND], tete_file, queue_file, cout_base_total;
    int flot_max_noeud[MAX_ND], arete_precedente[MAX_ND], distance_cout[MAX_ND];
    int degre[MAX_ND];
    bool visite[MAX_ND];

    inline void creer_arc(int depart, int arrivee, int cap, int cout_arc) {
        suivant[++compteur_aretes] = debut[depart];
        debut[depart] = compteur_aretes;
        destination[compteur_aretes] = arrivee;
        capacite[compteur_aretes] = cap;
        cout[compteur_aretes] = cout_arc;
    }

    inline void ajouter_arc_contraint(int u, int v, int borne_inf, int borne_sup, int cout_arc) {
        cout_base_total += borne_inf * cout_arc;
        degre[v] += borne_inf;
        degre[u] -= borne_inf;
        creer_arc(u, v, borne_sup - borne_inf, cout_arc);
        creer_arc(v, u, 0, -cout_arc);
    }

    inline bool spfa() {
        memset(distance_cout, 0x3f, sizeof distance_cout);
        memset(flot_max_noeud, 0x3f, sizeof flot_max_noeud);
        memset(visite, 0, sizeof visite);
        tete_file = 0, queue_file = 1;
        file[0] = source_2;
        distance_cout[source_2] = 0;

        while (tete_file != queue_file) {
            int u = file[tete_file++];
            if (tete_file == MAX_ND) tete_file = 0;
            visite[u] = false;

            for (int arete = debut[u]; arete; arete = suivant[arete]) {
                int v = destination[arete];
                int cout_chemin = distance_cout[u] + cout[arete];
                if (capacite[arete] > 0 && distance_cout[v] > cout_chemin) {
                    distance_cout[v] = cout_chemin;
                    flot_max_noeud[v] = std::min(flot_max_noeud[u], capacite[arete]);
                    arete_precedente[v] = arete ^ 1;
                    if (!visite[v]) {
                        visite[v] = true;
                        file[queue_file++] = v;
                        if (queue_file == MAX_ND) queue_file = 0;
                    }
                }
            }
        }
        return distance_cout[puits_2] < INT_MAX;
    }

    inline int resoudre() {
        // Arc de contrôle du flot
        creer_arc(puits_originale, source_originale, INT_MAX, 0);
        creer_arc(source_originale, puits_originale, 0, 0);

        // Construire le réseau auxiliaire
        for (int i = 1; i <= nb_noeuds; ++i) {
            if (degre[i] > 0) {
                creer_arc(source_aux, i, degre[i], 0);
                creer_arc(i, source_aux, 0, 0);
            } else if (degre[i] < 0) {
                creer_arc(i, puits_aux, -degre[i], 0);
                creer_arc(puits_aux, i, 0, 0);
            }
        }

        int cout_total = cout_base_total;
        source_2 = source_aux;
        puits_2 = puits_aux;

        while (spfa()) {
            // Augmenter le long du chemin trouvé
            cout_total += distance_cout[puits_2] * flot_max_noeud[puits_2];
            for (int noeud = puits_2; noeud != source_2; noeud = destination[arete_precedente[noeud]]) {
                capacite[arete_precedente[noeud]] += flot_max_noeud[puits_2];
                capacite[arete_precedente[noeud] ^ 1] -= flot_max_noeud[puits_2];
            }
        }
        return cout_total;
    }
}