import sys

def bellman_ford_modifie(source, puit, capacites, demandes, couts):
    n = len(capacites)
    m = len(demandes)
    
    # Initialisation du flot et des coûts réduits
    f = [[0] * m for _ in range(n)]  # Matrice de flot initialisée à zéro
    u = [[0] * m for _ in range(n)]  # Matrice des coûts réduits initialisée à zéro
    
    # Fonction pour calculer les coûts réduits u
    def calculer_couts_reduits():
        nonlocal u
        u = [[couts[i][j] + u[i][j] for j in range(m)] for i in range(n)]
        return u
    
    # Fonction pour construire le réseau auxiliaire R*
    def construire_reseau_auxiliaire(f):
        R_star = [[0] * (n + m) for _ in range(n + m)]
        for i in range(n):
            for j in range(m):
                if f[i][j] < capacites[i]:
                    R_star[i][n + j] = capacites[i] - f[i][j]
                if f[i][j] > 0:
                    R_star[n + j][i] = f[i][j]
        return R_star
    
    # Fonction pour déterminer s'il existe un chemin de s à t dans R*
    def chemin_de_s_a_t(R_star):
        visited = [False] * (n + m)
        queue = [source]
        visited[source] = True
        parent = [-1] * (n + m)
        
        while queue:
            node = queue.pop(0)
            
            if node == puit:
                chemin = []
                while node != -1:
                    chemin.append(node)
                    node = parent[node]
                chemin.reverse()
                return True, chemin
            
            for v in range(n + m):
                if not visited[v] and R_star[node][v] > 0:
                    queue.append(v)
                    visited[v] = True
                    parent[v] = node
        
        return False, None
    
    # Fonction pour mettre à jour le flot f selon le chemin trouvé
    def mettre_a_jour_flot(chemin, delta):
        for k in range(len(chemin) - 1):
            i = chemin[k]
            j = chemin[k + 1]
            if i < n and j >= n and j < n + m:
                f[i][j - n] += delta
            elif j < n and i >= n and i < n + m:
                f[j][i - n] -= delta
    
    # Algorithme principal pour résoudre le problème de flot maximum à coût minimum
    while True:
        R_star = construire_reseau_auxiliaire(f)
        existe_chemin, chemin = chemin_de_s_a_t(R_star)
        
        if not existe_chemin:
            break
        
        delta = min(R_star[chemin[k]][chemin[k + 1]] for k in range(len(chemin) - 1))
        mettre_a_jour_flot(chemin, delta)
    
    # Calcul du coût total du flot
    cout_total = sum(f[i][j] * couts[i][j] for i in range(n) for j in range(m) if f[i][j] > 0)
    
    return f, cout_total

# Exemple d'utilisation du script pour tester l'algorithme
def exemple_utilisation():
    # Exemple de réseau de distribution avec des paramètres aléatoires
    n = 3  # Nombre d'entrepôts
    m = 4  # Nombre de clients
    capacites = [10, 8, 12]  # Capacités des entrepôts
    demandes = [7, 5, 8, 6]  # Demandes des clients
    couts = [
        [0, 2, 4, 0],   # Coûts pour le premier entrepôt
        [3, 0, 0, 1],   # Coûts pour le deuxième entrepôt
        [0, 0, 2, 5]    # Coûts pour le troisième entrepôt
    ]
    
    # Calcul du flot maximum à coût minimum
    source = 0
    puit = m  # Le puits est le dernier client dans cet exemple
    
    flot_final, cout_total = bellman_ford_modifie(source, puit, capacites, demandes, couts)
    
    # Affichage des résultats
    print("Flot final (matrice de flot) :")
    for ligne in flot_final:
        print(ligne)
    print(f"Coût total du flot : {cout_total}")

# Exécuter l'exemple d'utilisation si le script est exécuté directement
exemple_utilisation()