Explained: Hungarian Algorithm (quazi) schema for Bi-Graph
IntuitionLeverage a greedy approach that maximizes the total score.ApproachThe solution employs a bipartite graph matching algorithm with the following key step
# Intuition\nLeverage a greedy approach that maximizes the total score.\n\n# Approach\nThe solution employs a bipartite graph matching algorithm with the following key steps:\n\n1. Greedy Value Selection\n   - Process values from highest to lowest\n   - Proves optimal because at each step, including the maximum available unused value leads to the best possible solution\n   - If a high-value cell can be selected without violating constraints, it should always be included\n\n2. Bipartite Graph Construction\n   - Create a bipartite graph with two vertex sets:\n     * Rows: [0 to N-1]\n     * Values: [N to N+M]\n   - Initial edges represent possible value-to-row mappings\n   - Oriented graph allows tracking of selection possibilities\n\n3. Augmenting Path Algorithm\n   - Similar to Hungarian Algorithm for maximum matching\n   - Uses Breadth-First Search (BFS) to find augmenting paths\n   - Dynamic path reconstruction to maximize score\n   - Key steps:\n     * Explore possible paths from highest values\n     * Modify graph connections to reflect selections\n     * Ensure no row or value is reused\n\n## Algorithmic References\n- Similar Algorithms:\n  1. Hungarian Algorithm (Kuhn-Munkres Algorithm)\n  2. Hopcroft-Karp Maximum Matching Algorithm\n  3. Ford-Fulkerson Path Augmentation Technique\n\n# Complexity\n- Time Complexity: $$O(N \\cdot M \\cdot (N+M))$$\n  * N: Number of rows\n  * M: Maximum value in the grid\n  * Nested loops for graph construction and path finding\n  * Each value processed with a BFS traversal\n\n- Space Complexity: $$O(N + M)$$\n  * Graph representation\n  * Parent tracking vector\n  * Queue for BFS\n\n# Mathematical Formulation\nLet $$G = (V_R, V_V, E)$$ be the bipartite graph where:\n- $$V_R$$: Set of rows\n- $$V_V$$: Set of values\n- $$E \\subseteq V_V \\times V_R$$: Edges representing possible selections\n\nThe goal is to find a maximum weight independent set $$S \\subseteq E$$ such that:\n- No two edges in $$S$$ share a vertex in $$V_R$$\n- Total weight $$\\sum_{(v,r) \\in S} v$$ is maximized\n\n# Proof Sketch of Optimality\nKey Observation: \n- By processing values in descending order\n- Greedily selecting highest available unique values\n- Dynamically reconstructing paths\n- The algorithm guarantees a globally optimal solution\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int maxScore(const vector<vector<int>>& grid) {\n        const int N = grid.size();\n        const int M = accumulate(\n            grid.begin(), grid.end(), 0,\n            [](int acc, const auto& v) { return max(acc, *max_element(v.begin(), v.end())); });\n\n        // Create a bipartite graph representation\n        // Vertices are split into two sets:\n        // - Rows: [0 .. N-1]\n        // - Values: [N .. N+M]\n        // This allows mapping unique values to rows\n        vector<unordered_set<int>> gr(N + M + 1);\n        for (int i = 0; i < N; ++i)\n            for (int e : grid[i])\n                // Populate oriented edges in bipartite graph from value to rows\n                gr[e + N].insert(i);\n\n        int res = 0;\n\n        // Process values from highest to lowest for greedy selection\n        for (int val = M; val >= 0; --val) {\n            if (gr[val + N].empty()) continue;\n\n            // Parent tracking for path augmentation\n            // -2: unvisited, -1: source vertex\n            vector<int> parent(gr.size(), -2);\n            parent[val + N] = -1;\n\n            // BFS to find augmenting path\n            queue<int> q;\n            q.push(val + N);\n            while (!q.empty()) {\n                int u = q.front();\n                q.pop();\n\n                // If we reach an empty row, we can augment the path\n                if (u < N && gr[u].empty()) {\n                    for (int p = parent[u]; p > -1; u = p) {\n                        p = parent[u];\n                        if (p < 0) break;\n                        // Swap edge directions u -> p while deleting original\n                        gr[u].insert(p);\n                        gr[p].erase(u);\n                    }\n                    res += val; // Add the current value to the total score\n                    break;\n                }\n\n                for (int v : gr[u]) if (parent[v] < -1) { // Proceed with BFS\n                    parent[v] = u;\n                    q.push(v);\n                }\n            }\n        }\n\n        return res;\n    }\n};\n\n```
['C++']