405222: GYM101848 F Hack

This seems to be a classic problem in graph theory.

You are given a simple bipartite graph. For each operation you can select a perfect match from the graph and delete it (by deleting all edges in the match). How many times at most can you do such operation?

Specifically, you are given the graph in the following way: we number nodes on the left side 1 to n and nodes on the right side also 1 to n. Edge (i, j) denotes an edge connecting the i-th node on the left side with the j-th node on the right side.

An algorithm, which is obviously ridiculous, adopts the following greedy strategy:

1. Set the answer to be 0.
2. Use Hungarian algorithm to find a perfect match. Return the answer if failed; otherwise increase the answer.
3. Delete the edges in the perfect match, and return to step 2.

You might see that this algorithm sometimes fails to find the optimal solution because at some point, it deletes the "wrong" match when there are multiple options available. However, the perfect match Hungarian will find is closely related to the numbering order of the nodes, at least in our implementation. So, to make it sound more promising, we can adopt a random algorithm that shuffles the node numbers repeatedly, runs the algorithm above and tries to update the answer every time. The algorithm exits when the optimal solution refuses to update in at least 10 recent iterations.

The following is a C++ implementation of this solution. The problem guarantees that we use the checker adopting the same code as provided below.

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> P;
const int maxn = 300;

struct Bipartite {
    // This is just a simple hungarian algorithm.
    int from[maxn], use[maxn], mat[maxn][maxn], n, tot;

    bool match(int x) {
        for (int v = 1; v <= n; ++v)
            if (mat[x][v] && !use[v]) {
                use[v] = 1;
                if (from[v] == -1 || match(from[v])) {
                    from[v] = x;
                    return 1;
                }
            }
        return 0;
    }

    void delete_match() {
        for (int i = 1; i <= n; ++i)
            mat[from[i]][i] = 0;
    }

    int hungary() {
        tot = 0;
        memset(from, -1, sizeof from);
        for (int i = 1; i <= n; ++i) {
            memset(use, 0, sizeof use);
            if (match(i)) ++tot;
        }
        return tot;
    }

    void init(int n) {
        memset(mat, 0, sizeof mat);
        this->n = n;
    }

    void add_edge(int u, int v) {
        mat[v] = 1;
    }
} bp;

int solve_bipartite_annealing(int n, vector<P> edges) {
    // Example: solve_bipartite_annealing(3, {{1, 1}, {2, 2}, {3, 2}, {3, 3}});
    int temperature = 10, best = 0;
    int permutation[maxn];
    iota(permutation + 1, permutation + n + 1, 1); // permutation = [1, 2, 3, ...]

    while (temperature > 0) {
        temperature–;
        bp.init(n);
        random_shuffle(permutation + 1, permutation + n + 1);
    		// permutation[1..n] is a random permutation of 1..n

        for (P &e: edges)
            bp.add_edge(e.first, permutation[e.second]);
        int current_ans = 0;
        while (bp.hungary() == n) {  // a perfect match found
            current_ans++;  // increase answer
            bp.delete_match();  // delete matching edges
        }
        if (current_ans > best) {  // a better solution found
            best = current_ans;
            temperature = 10;  // nice, we are motivated!
        }
    }
    return best;
}

Please construct a test case such that this algorithm does not find the optimal under at least 100 random seeds. As this is a classical problem, the jury, of course, know how to solve it correctly. You pass one test when the random algorithm yields a different answer from the correct one under one given random seed.

Random seed here.

3 4
1 1
2 2
3 2
3 3