L'analyse d'un problème de type réseau de flux met en évidence une réduction à un problème d'optimisation. La solution consiste à construire un graphe auxiliaire avec une source et un puits fictifs pour gérer les déséquilibres de flux. Chaque arc original est modélisé par plusieurs arêtes possibles pour permettre la correction du flux et de la capacité à moindre coût.

struct Edge {
    int from, to;
    long long capacity, cost;
    long long flow;
};

vector<Edge> edges;
vector<vector<int>> graph;

void add_edge(int u, int v, long long cap, long long cst) {
    graph[u].push_back(edges.size());
    edges.push_back({u, v, cap, cst, 0});
    graph[v].push_back(edges.size());
    edges.push_back({v, u, 0, -cst, 0});
}

pair<long long, long long> min_cost_max_flow(int source, int sink, int n) {
    const long long INF = 1e18;
    long long total_cost = 0, total_flow = 0;
    vector<long long> potential(n, 0);

    while (true) {
        vector<long long> dist(n, INF);
        vector<int> prev_edge(n, -1);
        vector<bool> in_queue(n, false);
        queue<int> q;
        
        dist[source] = 0;
        q.push(source);
        in_queue[source] = true;
        
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            in_queue[u] = false;
            
            for (int idx : graph[u]) {
                Edge &e = edges[idx];
                if (e.flow < e.capacity) {
                    long long adjusted_cost = e.cost + potential[u] - potential[e.to];
                    if (dist[u] + adjusted_cost < dist[e.to]) {
                        dist[e.to] = dist[u] + adjusted_cost;
                        prev_edge[e.to] = idx;
                        if (!in_queue[e.to]) {
                            q.push(e.to);
                            in_queue[e.to] = true;
                        }
                    }
                }
            }
        }
        
        if (dist[sink] == INF) break;
        
        for (int i = 0; i < n; ++i) {
            if (dist[i] < INF) potential[i] += dist[i];
        }
        
        long long path_flow = INF;
        for (int v = sink; v != source; v = edges[prev_edge[v]].from) {
            path_flow = min(path_flow, edges[prev_edge[v]].capacity - edges[prev_edge[v]].flow);
        }
        
        for (int v = sink; v != source; v = edges[prev_edge[v]].from) {
            edges[prev_edge[v]].flow += path_flow;
            edges[prev_edge[v] ^ 1].flow -= path_flow;
            total_cost += path_flow * edges[prev_edge[v]].cost;
        }
        
        total_flow += path_flow;
    }
    
    return {total_flow, total_cost};
}

Pour un problème de planification avec des contraintes de zone, une formulation en coupe minimale est appropriée. La construction du graphe sépare les décisions pour chaque emplacement en créant une chaîne de nœuds représentant les hauteurs possibles. Des arêtes de capacité infinie imposent les restrictions de hauteur maximale, tandis que des arêtes vers le puits modélisent les pénalités.

void build_zone_graph(vector<vector<int>>& adjacency, vector<int>& penalties,
                      int num_locations, int max_height) {
    int source = 0;
    int sink = num_locations * (max_height + 1) + 1;
    int node_count = sink + 1;
    
    adjacency.resize(node_count);
    
    for (int loc = 0; loc < num_locations; ++loc) {
        int prev_node = source;
        for (int h = 1; h <= max_height; ++h) {
            int current_node = loc * (max_height + 1) + h;
            adjacency[prev_node].push_back(current_node);
            adjacency[current_node].push_back(prev_node);
            prev_node = current_node;
        }
        adjacency[prev_node].push_back(sink);
        adjacency[sink].push_back(prev_node);
    }
}

L'étude des problèmes de chaînes de caractères nécessite une compréhension approfondie des structures automates comme les suffix-automates. Pour compter les sous-chaînes distinctes dans une plage donnée, une approche hybride combinant le suffix-automate avec une gestion dynamique des positions de fin permet d'obtenir une solution efficace.

class DynamicSuffixAutomaton {
    struct State {
        map<char, int> transitions;
        int link, length;
        set<int> end_positions;
    };
    
    vector<State> automaton;
    int last;
    
public:
    DynamicSuffixAutomaton() {
        automaton.push_back({{}, -1, 0, {}});
        last = 0;
    }
    
    void extend(char c, int position) {
        int current = automaton.size();
        automaton.push_back({{}, 0, automaton[last].length + 1, {position}});
        
        int p = last;
        while (p != -1 && !automaton[p].transitions.count(c)) {
            automaton[p].transitions[c] = current;
            p = automaton[p].link;
        }
        
        if (p == -1) {
            automaton[current].link = 0;
        } else {
            int q = automaton[p].transitions[c];
            if (automaton[p].length + 1 == automaton[q].length) {
                automaton[current].link = q;
            } else {
                int clone = automaton.size();
                automaton.push_back(automaton[q]);
                automaton[clone].length = automaton[p].length + 1;
                automaton[clone].end_positions.clear();
                
                while (p != -1 && automaton[p].transitions[c] == q) {
                    automaton[p].transitions[c] = clone;
                    p = automaton[p].link;
                }
                
                automaton[q].link = automaton[current].link = clone;
            }
        }
        
        last = current;
    }
    
    long long count_distinct_in_range(int left, int right) {
        long long result = 0;
        for (const auto& state : automaton) {
            if (state.link != -1) {
                int max_match = 0;
                for (int pos : state.end_positions) {
                    if (pos >= left) {
                        max_match = max(max_match, min(state.length, right - pos + 1));
                    }
                }
                if (max_match > automaton[state.link].length) {
                    result += max_match - automaton[state.link].length;
                }
            }
        }
        return result;
    }
};

La résolution de problèmes sur les arbres implique souvent une combinaison de techniques de parcours et de programmation dynamique. Pour les chemins avec des pénalités de transition, une approche récursive avec mémoisation sur les sous-arbres permet de capturer les différentes configurations possibles.

struct TreeDP {
    vector<vector<int>> children;
    vector<array<array<long long, 2>, 2>> memo;
    long long transition_cost;
    long long start_cost;
    
    void compute_dp(int node) {
        memo[node][0][0] = 0;
        memo[node][0][1] = start_cost;
        memo[node][1][0] = start_cost;
        memo[node][1][1] = start_cost;
        
        for (int child : children[node]) {
            compute_dp(child);
            
            array<array<long long, 2>, 2> new_dp = {{}};
            for (auto& row : new_dp) row.fill(LLONG_MAX);
            
            for (int ends_here : {0, 1}) {
                for (int starts_here : {0, 1}) {
                    for (int child_ends : {0, 1}) {
                        for (int child_starts : {0, 1}) {
                            long long current = memo[node][ends_here][starts_here];
                            long long child_val = memo[child][child_ends][child_starts];
                            
                            if (current == LLONG_MAX || child_val == LLONG_MAX) continue;
                            
                            long long penalty = 0;
                            if (starts_here && child_ends) penalty += transition_cost;
                            if (!starts_here && child_ends) penalty += start_cost;
                            if (starts_here && !child_ends) penalty += start_cost;
                            
                            int new_ends = ends_here || (starts_here && child_ends);
                            int new_starts = starts_here || (!child_ends && child_starts);
                            
                            new_dp[new_ends][new_starts] = min(
                                new_dp[new_ends][new_starts],
                                current + child_val + penalty
                            );
                        }
                    }
                }
            }
            
            memo[node] = new_dp;
        }
    }
};